Editorial for Krilca
Submitting an official solution before solving the problem yourself is a bannable offence.
Sa označimo realnu cenu jednog krilca, koju želimo da izračunamo.
Ako u -toj stavci menija piše da
krilaca košta
Juana, to znači da
krilaca realno ne mogu koštati manje od
Juana. Svaka manja realna cena za
krilaca zaokružena na najbliži ceo broj ne bi dala
kao rezultat zaokruživanja. Iz toga zaključujemo da je
, odnosno
.
Sada je potrebno proći kroz sve stavke u meniju i za svaku naći ovo donje ograničenje za cenu. Jasno je da najmanja moguća realna cena za jedno krilce ne sme biti manja od svakog tako dobijenog donjeg ograničenja, što znači da ne sme biti manja od njihovog maksimuma. Pošto nam se u zadatku garantuje da su cene u meniju formirane ispravno, to znači da je najmanja moguća realna cena jednog krilca jednaka upravo tom maksimumu.
R=\max_{i\in{1,2,\ldots,n}}(C_i-0.5/K_i)
Comments