Dat je niz koji se sastoji od celih brojeva i niz koji je na početku prazan. Želimo da iz niza prebacimo tačno elemenata u niz tako što ćemo puta ponoviti sledeću stvar:
- Izabrati nekih uzastopnih elemenata niza , a zatim najmanji od njih izbaciti iz niza i ubaciti u niz . Ukoliko ima više istih najmanjih elemenata među izabranih uzastopnih, može se izbaciti bilo koji.
Ovo želimo da uradimo na takav način da nakon izvršenih svih prebacivanja, razlika maksimalnog i minimalnog elementa u nizu bude najmanja moguća. Ispisati ovu najmanju razliku koju možemo da dobijemo ukoliko optimalno biramo operacije.
Opis ulaza
U prvoj liniji standardnog ulaza nalaze se tri broja odvojena razmakom , i . U drugoj liniji standardnog ulaza nalazi se brojeva odvojenih razmakom, koji predstavljaju niz .
Opis izlaza
U prvoj i jedinoj liniji standardnog izlaza ispisati najmanju razliku između maksimalnog i minimalnog elementa u nizu koju možemo da dobijemo optimalnim izborom operacija.
Primer
Standardni ulaz | Standardni izlaz | |
---|---|---|
5 3 2 10 8 7 12 1 |
1 | |
5 3 3 10 8 7 12 1 |
7 |
Objašnjenje test primera
U prvom test primeru u prvoj operaciji možemo izabrati podniz od kojih je najmanji broj i njega ćemo izbaciti iz niza i prebaciti u niz , nakon ovoga niz postaje . U drugoj operaciji sada moramo izabrati podniz od kojih je najmanji broj kog prebacujemo u niz . Niz je sada i razlika najvećeg i najmanjeg broja je .
U drugom test primeru možemo ponoviti iste operacije kao u prvom, u trećoj operaciji će nam samo ostati još da prebacimo minimum od u niz , što je broj , pa će nam niz biti gde je razlika izmeđeu najvećeg i najmanjeg broja .
Ograničenja i podzadaci
()
()
()
()
Test primeri su podeljeni u 4 disjunktne grupe:
U test primerima vrednim 15 poena: ().
U test primerima vrednim 30 poena: ().
U test primerima vrednim 30 poena: ().
U test primerima vrednim 25 poena: Nema dodatnih ograničenja.
Comments