magnify

Kaladėlių dėžutė

Pradinių duomenų failas:
kaladeles.in  
Rezultatų failas:
kaladeles.out  
Laiko apribojimas:
1 s.  
Atminties apribojimas:
16 Mb.  

Užduotis

Mažasis Linas mėgsta žaisti su savo kaladėlių dėžute. Jis deda kaladėles vieną ant kitos, šitaip pastatydamas įvairaus dydžio stulpus. „Žiūrėk, aš pastačiau sieną!“ – sako jis savo vyresnei sesei Giedrei. „Ne, tu turėtum sulyginti stulpų aukštį – tik tuomet tai būtų tikra siena“, atsako ji. Truputį pamąstęs Linas supranta, kad sesuo teisi. Taigi jam reikia perkelti kai kurias kaladėles, vieną po kitos, taip, kad galų gale visi stulpai būtų vienodo aukščio. Bet Linas – tingus berniukas ir jis nori atlikti darbą perkeldamas kuo mažiau kaladėlių. Ar galite jam padėti?

 

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas kaladėlių stulpų, kuriuos yra pastatęs Linas, skaičius N (1 <= N <= 50). Sekančioje eilutėje įrašytas N sveikųjų skaičių \(h_{1}\), \(h_{2}\), …, \(h_{N}\) – tai kiekvieno iš stulpelių aukščiai (1 <= \(h_{i}\) <= 100).

Bendras kaladėlių skaičius visuomet dalinsis iš stulpų skaičiaus, taigi visuomet bus įmanoma perkelti kaladėles taip, kad visi stulpai būtų vienodo aukščio.

Rezultatai

Pirmoje rezultatų failo eilutėje programa turi įrašyti, kiek minimaliai perkėlimų pakaks pastatyti sienai.

Pavyzdys

Pradiniai duomenys Rezultatai
6
5 2 4 1 7 5
5
© Bronė Narkevičienė