Dat je niz od kula kockica, kao na slici. Za svaku kulu je poznato od koliko je kockica sagrađena tj. koliko je visoka.
U jednom koraku se može izabrati bilo koji uzastopni niz kula i sa svake kule skinuti po 1 kockica ili na svaku kulu dodati po 1 kockica. To jest, izabrati i , i uzastopni podniz kula (gde označava visinu -te kule) promeniti na ili na .
Potrebno je odrediti najmanji broj koraka tako da sve kule postanu iste visine.
Opis ulaza
U prvoj liniji standardnog ulaza nalazi se prirodan broj koji označava broj kulica u nizu. U drugoj liniji nalazi se prirodnih brojeva razdvojenih razmakom , gde označava početnu visinu -te kule.
Opis izlaza
U prvoj i jednoj liniji standardnog izlaza ispisati najmanji broj potrebnih koraka da se sve kulice svedu da istu visinu.
Primeri
Standardni ulaz | Standardni izlaz | |
---|---|---|
4 6 7 4 5 |
3 | |
1 1000000000 |
0 |
Objašnjenje prvog test primera:
Jedan moguć najkraći niz koraka koji dovodi do kulica istih visina je:
- Sa kule broj 2 se izbaci 1 kockica.
- Sa kula broj 1 i 2 se izbaci po 1 kockica.
- Na kulu broj 3 se doda 1 kockica.
Slika niza kula na početku i nakon svakog od 3 koraka:
Ograničenja
,
Test primeri su podeljeni u 4 disjunktne grupe:
- U test primerima vrednim 20 poena: ,
- U test primerima vrednim 20 poena: ,
- U test primerima vrednim 40 poena:
- U test primerima vrednim 20 poena: Nema dodatnih ograničenja.
Comments