Editorial for Krilca


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Sa R označimo realnu cenu jednog krilca, koju želimo da izračunamo.

Ako u i-toj stavci menija piše da K_i krilaca košta C_i Juana, to znači da K_i krilaca realno ne mogu koštati manje od C_i-0.5 Juana. Svaka manja realna cena za K_i krilaca zaokružena na najbliži ceo broj ne bi dala C_i kao rezultat zaokruživanja. Iz toga zaključujemo da je K_i R \geq C_i-0.5, odnosno R \geq (C_i-0.5)/K_i.

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

There are no comments at the moment.