infoarena

http://acm.tju.edu.cn/toj/showp2832.html

Any hints?

E foarte usor sa calculez cum se primeste restul in mod optim. Negustorul nu are restrictii asupra numarului de monezi. (Knapsak clasic)

Cum pot sa calculez numarul optim de monezi cu care poate plati cumparatorul o anumita suma? El are restrictii la numarul de monezi de o anumita valoare. Daca as putea face asta as alege suma intre T si 2T care imi da numarul minim de monezi tranzactionate (cele folosite la platire + cele folosite la primirea restului).

Poti sa rezolvi problema in O(T * N) cu niste deque-uri.

Poate te ajuta solutia de la problema Ghiozdan: http://www.infoarena.ro/preoni-2007/runda-2/solutii