Национална олимпиада по информатика 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
|