[bankomati]

Znam deka proverkata so dinamicko i greedy na svaka
suma nece da radi, a drugu ideju nemam, znaci treba mi malo help.

Trebao bi i greedy da radis kao dinamicko. Znaci ako racunas G[k], onda nadjes najvecu novcanicu manju ili jednaku k (M[j]) i resenje ti je G[k-M[j]]+1.
Nadam se da sam pomogao.

Hvala ti mnogu, bas si mi pomognao

Nema na cemu!

Kako da pamtim niz koji je duzine vise od 500000

mozda

var a: array [1..500000] of longint;

Pa ne znam za free pascal, ali ovaj koji ja imam mi ne dozvoljava, a u Cu nisam probao. Ako moze onda OK.

Jedno pitanje: Ukoliko bankomat uvek ispisuje tachno reshenje, tj. ako treba ispisati 0, dokle treba ispitivati da bi se zakljuchilo da treba shtampati 0?

Ja mislim da najveci minimalni broj treba da bude (novacnica[n] div novcanica[n-1])+1+sgn(novcanica[n] mod novcanica[n-1]) to jest (k-1)*novcanica[n-1]>=novcanica[n] gde je novcanica sortiran u rastuci niz.

Ja sam ispitivao do 1000000

Hvala, sa tom granicom je mnogo bolje, sad mi samo drugi primer pada na vremenu.

Pa kako moze da ti pada na vremenu kad ne odi nad 1000000?
Mrzelo me da proveravam na koj nacin ti rade program, ali ti je nepotrebno
iskompliciran. Mislim dosta je da primenis ono sto je boba napisao,
nesto ovako:

b[0]=0
for i=1 to 1000000 do begin
b[i]=1000000
m=0
for j=1 to br_novcanica do
if a[j]<=i then
if b[i]>b[i-a[j]]+1 then
b[i]:=b[i-a[j]]+1
m=novcanica so maxvrednost pomala od i
if b[i-m]>b[i] then begin
writeln(i)
break
end
end

a[i] je vrednost na novcanica i
b[i] najmal broj na novcanica so koi se dobije suma i

Bas sam proverio: na vtori test primer odgovor je 0.

Hvala na trudu, reshila sam zadatak.

meni stalno pada samo 8. test primjer. mogu li ga dobiti na private?

A zar nije logicnije (meni je palo na pamet, implemetirao sam i proslo je) da se proveravaju sume iz intervala [1,A], gdje je A ukupan zbir svih vrednosti unetih novcanica?

Jer, ukoliko bankomat ispacuje sve sume iz tog intervala na pravilan nacin, on ce svaku sumu K (K>A) moci da rastavi kao K+A popuni K, pa onda A (a to uvjek radi na pravilan nacin).

Nisam neki matematicar (sad mi se profesorica smeje na sav glas ;) ), ali mislim da za ovo ne postoji kontradikcija. Postoji li?

n ide do 50 a svaka novcanica do 500000, sto ce reci da to nikako nije bolje posto ta suma A moze biti bas bas velika.. Jedino mozes gledati sta je manje, A ili dokle inace ides (ako ta pretpostavka valja ) i to bi bila neka optimizacija u slucaju da ti se nameste test primeri za to.

Da, tu si u pravu... Ali eto, meni je fino proslo.

Sad primetih da je i Relja napisao "...ako ta pretpostavka valja..."

Moze li neko da dokaze/opovrgne ovo gore sto sam napisao, cisto da znaju oni koje ce ovo nekad citati? Hvala.

El moze neko da mi da 8. test primer, jer nikako da ukapiram sta ne radi a sve ostalo mi prolazi.

Ne treba. Reseno!!!

hmm, imam time limit na 6/10 iako mi radi u const vremenu za sve, ajd ako nekog ne mrzi nek pogleda zadnji submision moj xD

Zanemarite zadnji post, nasao sam gresku :P

a do kog broja treba da se dinamicki proverava? msm kako znate da je do 1000000 dovoljno?

Ako postoji resenje , ono ce biti u intervalu od [1, 2 * MaxNovcanica] .

hmm ja sam malo razmisljao i ja mislim da je to interval 2*druga po velicini novcanica...nisam bas siguran da li mogu bas potpuno korektno da dokazem...a jel ima neki dokaz za ovo sto ti kazes?

Hm , nemam dokaz, samo logiku . Nismo ni ti ni ja u pravu maksimalna vrednost ( po mojoj logici ) bi trebala da bude izmedju 2 * DrugaPoVelicini i 2 * PrvaPoVelicini ali posto ne znam tacno gde ja uzimam maksimum za granicu tj granica intervala mi je 2 * PrvaPoVelicini ...

pa nzm...cu da potrazim po internetu malo za neki dokaz:D

evo nasao granice za proveru
About all that is known about the mathematical structure of this problem is that if c1 < c2 < ... < cm are the coin denominations, and the greedy algorithm is not optimal, then there is a counterexample (an amount for which the greedy algorithm gives more coins than are necessary) between (c3+2) and (cm+cm-1-1), inclusive.