Mai mult de jumatate dintre voi ati rezolvat corect problema si va
felicit. Totusi, va reamintesc inca o data sa nu uitati sa explicati
algoritmul de rezolvare la inceputul sursei. In felul acesta, pot intelege
mai usor ceea ce ati scris in program si pot compara diferitii algoritmi.
Multumesc mult celor care si-au explicat algoritmul si de asemenea ii
transmit lui Catalin Alexandru faptul ca nu mi s-a parut deloc interesanta
sursa lui de 4 linii de cate 500 de caractere fiecare.
   Acum sa trecem la rezolvarea problemei. Am vazut ca multi dintre voi
au redus problema aceasta la problema rucsacului. In acest caz, rucsacul
are o capacitate egala cu suma kilogramelor tuturor celor p conserve
(deci cel mult 300*200=60000), iar greutatile sunt chiar greutatile
celor p conserve. In acest caz, complexitatea este O(p*p*C), unde C este
capacitatea maxima a unei conserve (in cazul nostru 200). Aceasta
complexitate este destul de mare si pe anumite teste nu intra in timp.
Remarcam de asemenea ca aceasta complexitate nu depinde de n, numarul de
alpinisti.
   Solutia la care m-am gandit eu are complexitatea de O(n*p). Nu o sa
descriu in detaliu aceasta solutie, ci va voi lasa pe voi sa va ganditi
la ea, dandu-va totusi o informatie importanta: metoda foloseste o
matrice A cu p linii si n coloane.
   Sunt convins ca ati gasit si alte solutii si as fi bucuros sa le
aflu.