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