Kako se radi C zadatak sa takmicenja Hello 2018 na CodeForces?
Neka je dp[i] najjeftiniji nacin da kupis 2^i litara limunade.
Inicijalizuj resenje na 0.
Radi for petlju od 0 do 30.
Ako je dp[i]<sol, sol=dp[i].
Ako je L&(1<<i), sol+=dp[i].
Moj kod: http://codeforces.com/contest/913/submission/34032002
1 Like
Evo jos jedno resenje(greedy), ovako sam ja radio:
Prvo sortiramo sve flase limuade rastuce po ceni po litru. Zatim ides kroz taj sortirani niz(neka je taj niz c):
Ako je c[i] <= L (treba nam ukupno L litara), to predstavlja najbolju ponudu da kupis limunadu (jer je niz sortiran rastuce, a nama treba najmanja cena), pa ces uzeti maksimalan broj tih flasa koji mozes da uzmes. Samo ostaje da proveris da li dobijas bolju(manju) cenu ukoliko uzmes maks + 1 tih flasa.
Naravno, svaki put kad ponovimo ovaj postupak smanjujemo L za kolicinu kupljene limunade.
S druge strane, ako je c[i] > L, jedino sto treba da uradimo je da proverimo da li ako kupimo jednu tu flasu dobijamo manju cenu(svakako cemo prekoraciti L).
Evo linka do mog resenja http://codeforces.com/contest/913/submission/34057299