Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 2832. The Fewest Coins  (Citit de 11178 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
popoiu.george
Vorbaret
****

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« : Noiembrie 12, 2013, 23:33:02 »

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).
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #1 : Decembrie 10, 2013, 18:40:08 »

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
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines