h3. (problema medie, clasa a 9-a)

La prima vedere, problema este asemanatoare cu problema 'rucsacului':http://en.wikipedia.org/wiki/Knapsack_problem, deci se poate aborda folosind metoda programarii dinamice. Avand in vedere limita mare pentru numarul $L$ o astfel de abordare nu ar fi obtinut punctaj maxim.   Avand in vedere ca toate monezile sunt puteri ale numarului $C$, exista o rezolvare greedy: se determina cel mai mare tip de moneda $C^A{~i~}^$ disponibil si se foloseste un numar maxim posibil de astfel de monede (minimul dintre $L/C^A{~i~}^$ si $B{~i~}$). Complexitatea unei astfel de solutii este $O(log{~C~} L)$.

La prima vedere, problema este asemanatoare cu problema 'rucsacului':http://en.wikipedia.org/wiki/Knapsack_problem, deci se poate aborda folosind metoda programarii dinamice. Avand in vedere limita mare pentru numarul $L$ o astfel de abordare nu ar fi obtinut punctaj maxim.   Avand in vedere ca toate monezile sunt puteri ale numarului $C$, exista o rezolvare greedy: se determina cel mai mare tip de moneda $C^A{~i~}^$ disponibil si se foloseste un numar maxim posibil de astfel de monede (minimul dintre $L/C^A{~i~}^$ si $B{~i~}$). Complexitatea unei astfel de solutii este $O(log{~C~} L)$. O solutie care ar fi efectuat scaderi repetate ale cele mai mari monezi ar fi obtinut de asemenea punctaj maxim.

h2. 'Dezastru':problema/dezastru