borcane pe scari
Rares Vernica
In problemam asta se cere sa va ganditi cum cresc functiile.
---
Se da un set de k borcane identice si o scara cu n trepte. Trebuie sa
aflati care este trapta cea mai inalta de pe care puteti da drumul la
un borcan si el sa nu se sparga.
Puteti foarte usor sa va imaginati o strategie in care minimizati
numarul de aruncari folosind cautara binara. Astfel, aruncati borcanul
de pe treapta din mijloc. Daca se sparge trebuie sa cautati in
treptele de sub ea. Daca nu, trebuie sa cautati in treptele de
deasupra ei. In acest fel ve-ti executa cel mult log(n) aruncari. Pe
de alta parte ve-ti sparge log(n) borcane.
O strategie care minimizeaza numarul de borcane sparte ar fi
urmatoarea. Aruncati borcanul de pe fiecare treapta mergand de jos in
sus. In momentul in care borcanul se sparge stiti ca treapta cautata e
cea de sub treapta curenta. In felul acest spargeti cel mult 1 borcan,
dar s-ar putea sa efectuati n aruncari.
Intrbare.
Cosiderand ca aveti la dispozitie doar 2 borcane (k = 2), propuneti o
strategie de gasire a treptei care sa necesite f(n) aruncari, astfel
incat f(n) sa creasca mai incet decat liniar (adica, lim(n->inf)
f(n)/n = 0).
---
Rares
P.S. Daca vreti va pot zice solutia la problema cu palariile.