ŽUPANIJSKO NATJECANJE 2013. / Srednja škola, II. podskupina (3. i 4. razred) - 1. zadatak

Digitalni audio signal se u računalu pohranjuje kao niz cijelih brojeva dobiven uzimanjem uzoraka analognog signala određenom frekvencijom.

Kako je za kvalitetan signal potrebna visoka frekvencija (npr. audio CD-i pohranjuju 44,056 16-bitnih brojeva po sekundi) tih brojeva može biti jako puno pa postoje razni algoritmi za sažimanje tog niza.

U ovom zadatku ćemo opisati jedan vrlo jednostavan algoritam sažimanja.

Neka je zadan niz od N prirodnih brojeva. Počevši od početka niza sažimanje se vrši na sljedeći način:

1. Odredimo blok uzastopnih sljedbenika, redom od trenutne pozicije u nizu. Na primjer, ako je zadan niz (1, 2, 3, 2) onda će prvi blok biti (1, 2, 3), a ako je zadan niz (2, 1, 2), onda će prvi blok biti samo (2).

2. Sažimamo i ispisujemo trenutni blok na sljedeći način:

   a. Ukoliko se blok sastoji od samo jednog broja onda ispisujemo taj broj.

   b. Ukoliko svi brojevi iz bloka imaju isti broj znamenki, te svi počinju s istom znamenkom:

   i. Odredimo prefiks bloka – najduži niz znamenki s kojim počinje svaki od brojeva. Na primjer, prefiks bloka (231, 232, 233) je '23'.

   ii. Ispišemo prefiks bloka s repom koji se sastoji od ostalih znamenaka najmanjeg i najvećeg broja u bloku odvojenih znakom '-' (minus). Tako je, na primjer, rep bloka (231, 232, 233) jednak '1-3', te za cjelokupni blok ispisujemo '231-3'.

c. Ukoliko svi brojevi iz bloka nemaju isti broj znamenki ili ne počinju svi s istom znamenkom ispisujemo najmanji i najveći broj iz bloka odvojene znakom '-' (minus).

1. Trenutno ispisani blok uklanjamo iz niza te dalje nastavljamo dok ne prođemo kroz cijeli niz.

Na primjer, ako je zadan niz (1, 2, 4, 10, 11, 12) tada će prvi blok biti sažet i ispisan kao '1-2' (pravilo c), drugi blok kao '4' (pravilo a), a treći kao '10-2' (pravilo b).

Napišite program koji sažima i ispisuje sažetak zadanog niza prirodnih brojeva.

Ulazni podaci

U prvom retku ulaza nalazi se prirodan broj N (1 ≤ N ≤ 100 000) – duljina zadanog niza.

Svaki od sljedećih N redova sadrži jedan prirodan broj Ti (1 ≤ Ti ≤ 10 000 000) – odgovarajući broj u nizu.

Izlazni podaci

Broj redaka u izlazu treba odgovarati broju blokova u sažetku zadanog niza.

Svaki redak u izlazu treba sadržavati sažetak odgovarajućeg bloka kako je opisano u tekstu zadatka.

Primjeri test podataka

Ulaz

8
1
2
3
4
122239
122240
122241
122256

Izlaz

1-4
122239-41
122256

Ulaz

10
1
2
3
3
2
1
9
10
13
10000

Izlaz

1-3
3
2
1
9-10
13
10000