Kul kule
vreme | memorija | ulaz | izlaz |
---|---|---|---|
1 s | 64 Mb | standardni izlaz | standardni ulaz |
Kao što je većini đaka poznato, draga profesorka robotike Katarina mnogo voli da se igra lego robotima i kockicama. Ovaj put na čas je donela specijalnog robota i kula kockica. Na svakoj kuli se nalazi određen broj naslaganih kockica koje predstavljaju visinu te kule, tačnije -ta kula ima visinu (sastavljena je od tačno kockica). Đaci su primetili da ne sadrže sve kule podjednak broj kockica i žele to da promene pomoću profesorkinog specijalnog robota. Naime, ovaj robot može izvršiti sledeću operaciju:
- Robot može da uzme dve ili tri kockice sa beskonačne gomile koja se nalazi pored datih kula (Katarina toliko voli kockice da ih ima u neograničenim količinama) i da te kockice stavi na jednu od kula. Tako se u jednoj operaciji povećava visina određene kule za ili kockice.
Kako su đaci i sama profesroka malo nestrpljivi, molimo vas pomozite im da što pre izračunaju minimalan broj operacija potrebnih robotu da izjednači visine svih kula.
Opis ulaza
U prvom redu standardnog ulaza nalazi se prirodan broj , broj kula koje je donela profesorka. U drugom redu nalazi se niz od prirodnih brojeva razdvojenih razmakom, gde predstavlja visinu -te kule.
Opis izlaza
U prvom i jedinom redu standardnog izlaza ispisati ceo broj koji predstavlja minimalan broj operacija navedenih u tekstu zadatka potrebnih robotu da izjednači visine svih kula.
Primeri
7 10 5 3
1 5 1 5 2 5
Objašnjenje primera
U prvom primeru ukupno imamo kule sa kockicama. Prva kula je visine , druga kula je visine , dok je treća kula visine . Robot može izjednačiti visine kula u operacije :
- Robot dodaje kockice na prvu kulu. Sada su visine kula { , , }.
- Robot dodaje kockice na treću kulu. Trenutne visine kula su { , , }.
- Robot dodaje kockice na treću kulu. Konačne visine kula su { , , }.
Pokazali smo kako robot može da izjednači visine kula u operacije, može se pokazati da je nemoguće izjednačiti pomenute kule u manje poteza. Minimalan broj potrebnih operacija je .
Ograničenja
Test primeri su podeljeni u dve disjunktne gurpe:
- U test primerima koji vrede poena važiće i .
- U test primerima koji vrede poena važiće i .
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.