ŠKOLSKO NATJECANJE 2016 / Srednja škola, II. podskupina (3. i 4. razred) - 2. zadatak

Prilikom kodiranja video zapisa koristeći MPEG-1 standard, dopuštena su tri različita načina zapisa pojedinih slika: takozvana I-slika se samostalno kodira, P-slika se kodira tako da se opisuje razlika od prethodne slike, B-slika se kodira tako se opisuju razlike od prethodne i od sljedeće slike. U ovom zadatku koristimo sličnu ideju za kodiranje običnog niza cijelih brojeva.

Niz od N cijelih brojeva kodiramo pomoću N naredbi tako da i-ta naredba kodira i-ti broj. Postoje tri različite naredbe:

• I x — kodira broj x

• P x — kodira broj za x veći od prethodnog broja u nizu

• B x — kodira broj za x veći od sljedećeg broja u nizu

Kako bi kodiranje bilo dobro definirano, ne smije se dogoditi da neposredno nakon naredbe tipa B dolazi naredba tipa P. Također, zahtijevamo da su prva i zadnja naredba u nizu tipa I. Ako niz naredbi zadovoljava ova dva uvjeta kažemo da je valjan. Tako je, na primjer, I 20, P -10, B 5, I 30 valjan niz naredbi koji kodira niz brojeva 20, 10, 35, 30.

Veličina niza naredbi je ukupan broj znakova u tom nizu izuzimajući znakove razmaka (dakle broje se slova, znamenke te znakovi minusa). Tako je, na primjer, veličina gornjeg niza naredbi jednaka 12. Zadan je niz brojeva, odredi najmanju moguću veličinu nekog valjanog niza naredbi koji ga kodira.

ULAZNI PODACI

U prvom redu nalazi se prirodni broj N \((2 \leq N \leq 100)\) — duljina zadanog niza brojeva. U K-tom od sljedećih K redova nalazi se broj Xk \((-10^{6} \leq Xk \leq 10^{6})\) — K-ti broj u nizu.

IZLAZNI PODACI

U prvi red ispišite jedan broj — traženu najmanju moguću veličinu.

BODOVANJE

U test podacima vrijednim 10% bodova najmanja moguća veličina se može postići koristeći samo naredbe tipa I. U dodatnim test podacima vrijednim 40% bodova najmanja moguća veličina se može postići koristeći samo naredbe tipa I i tipa P.

PRIMJERI TEST PODATAKA

ulaz

4
10
-20
3
1

izlaz

11

ulaz

5
-50
100
900
1000
-300

izlaz

21

ulaz

10
-5241
885
-2601
2079
2515
-8690
-9737
6750
-4813
-5314

izlaz

51