Текущ брой на Списание ИнфоМан
 


Национална олимпиада по информатика 2005, 3 кръг, Задача 1.3. ЗДРАВИНА

Уловието на задачата може да прочетете тук.

Решение

Нека означим с M броя нужни опити за определяне на Z. Тогава ако с g означим функцията, която решава задачата:

M = g(N,H)

За да решим задачата, нека разрешим една друга противоположна задача. Ако с f(N,M) означим максималната височина на кула, за която която може да се определи Z с N изделия и най-много M опита, можем да пресметнем f(N,M) с помощтта на следните връзки

f(1,M) = M - в най-лошия случай са необходими M опита. разполагаме само с 1 изделие и не можем да си позволим за прескочим част от кулата т.к. има риск да го счупим без да сме определили със сигурност Z.

f(X,1) = 1 - разполагаме само с 1 опит и някакъв брой изделия. Най-много за кула с височина 1 можем да определим със сигурност Z.

f(N,M) можем да пресметнем като използваме стойностите на f(N-1,M-1) и f(N,M-1). Това става по следния начин. Т.к. разполагаме с N>1 здрави изделия, решаваме да пуснем едно от тях от височина K. K го избираме по такъв начин, че ако изделието се счупи от височина K, да може със сигурност да се определи Z за частта от кулата до K-1 като има 1 изделие по-малко. Т.е. K<=f(N-1,M-1)+1. Същевременно т.к. искаме да получим максимална възможна стойност за f(N,M), трябва за частта от кулата над K да може да се определи Z със сигурност в случай, че изделието не се счупи от височина K. В този случай разполагаме с N изделия, но един опит по-малко - т.е. максималната част от кула над K е с височина f(N,M-1). По този начин получаваме f(N,M)=K+f(N,M-1). Т.к. искаме f(N,M) да е максимално, получаваме рекурентната връзка

f(N,M)=1+f(N-1,M-1)+f(N,M-1).

От тази връзка лесно се забелязва, че f(N,M) е нарастваща относно M. Затова при зададени N и H, можем да изпробваме последователно за всяко M от 1 до H, да пресметнем f(N,M) и вземем за отговор min i, за което f(N,i)>=H.

При решаване на задачата е необходимо да приложим техника динамично оптимиране за изчисляване на функцията f. Но ограниченията в условията са такива, че затруняват директното прилагане на тази техника. Следва да се забележат следните неща:

Когато N=1, директно пресмятаме g(1,H) = H. В останалите случаи търсим  min i, за което f(N,i)>=H. При този случай i със сигурност ще е по-малко или равно на 2*sqrt(H) и може последвателно да се изпробват стойностите за i. Друг важен момент е, че когато са дадени твърде много изделия (N>34), те се оказват ненужни т.к. с двоично търсене по височината на кулата ще са необходими най-много log2(H) от тях. Това на практика ограничава N до 34 при H<10^10.

Заб. с цел да се избегне stack overflow също е добра идея да се използва формула и за f(2,H)=(H*(H+1))/2

Примерна реализация


#include <iostream>
using namespace std;

bool c1[35][8192];
long long d1[35][8192];

long long dyn(int o, int i)
{
	if (o==1) return 1;
	if (i==1) return o;
	if (i==2) return ((long long)o*(long long)(o+1))/2;
	if (c1[i][o]) return d1[i][o];
	long long r = 1+dyn(o-1,i)+dyn(o-1,i-1);
	c1[i][o]=true; d1[i][o]=r;
    return r;
}

long long solve(int n, long long h)
{
	int i;
	if (n==1) return h;
	if (n>34) n=34;
	for (i=1;;i++)
	{
		long long r = dyn(i, n);
        if (r>=h) return i;
	}
}

int main(void)
{
	int n;
	long long h;
	cin>>n>>h;
	cout<<solve(n,h)<<endl;
	return 0;
}



Автор: Веселин Райчев


обратно към брой 27