Školsko natjecanje 2011. / Osnovna škola (8. razred) - 3. zadatak

Kornjača se sprema na još jednu utrku protiv Zeca, ovaj put na stazi s preprekama. Staza je podijeljena na segmente označene prirodnim brojevima, redom od 1 (startni segment) do 30000 (ciljni segment). Na svakom segmentu (osim startnog i ciljnog) može se ugraditi po jedna prepreka, koja ispunjava cijeli segment.

Kornjača je razmjestila N prepreka po stazi i zapisala oznake segmenata s preprekama. Nakon toga pretrčava stazu. Kada naiđe na prepreku, Kornjača je, naravno, mora preskočiti. Kako čuva snagu, Kornjača radi što kraće skokove. Međutim, ako su dvije prepreke na susjednim segmentima, Kornjača ne može skočiti između njih, nego ih mora preskočiti jednim skokom. Dakle, Kornjača će odskočiti sa zadnjeg segmenta ispred prepreke i doskočiti na prvi sljedeći segment na kojem nema prepreke.

Zec, naravno, želi sabotirati Kornjaču pa želi znati koliko je skokova Kornjača napravila, koliko segmenata je bio dug najdulji Kornjačin skok (ne brojeći odskočni i doskočni segment skoka), te oznaku prve prepreke (one najbliže startu) koju je preskočila u prvom najduljem skoku na stazi.

• ako je samo prvi red izlaza ispravan, a ostali nisu, test primjer donosi 50% bodova (ako prvi red nije ispravan, test primjer ne donosi bodove bez obzira na ispravnost ostalih redova);
• u test primjerima vrijednima 50% bodova, duljina najduljeg skoka će biti najviše dva segmenta.

Ulazni podaci

• prirodan broj N ($1 \leq N \leq 20$), broj prepreka na stazi;
• N različitih prirodnih brojeva, jedan ispod drugog – oznake segmenata na kojima se nalazi prepreka; oznake segmenata će biti između 2 i 29999, uključivo;

Izlazni podaci

• prvi red izlaza: prirodan broj – broj skokova koji je Kornjača napravila;
• drugi red izlaza: prirodan broj – duljina najduljeg skoka koji je Kornjača morala napraviti, u segmentima (bez odskočnog i doskočnog);
• treći red izlaza: prirodan broj – oznaka segmenta prve prepreke (one s najmanjom oznakom) preko koje je Kornjača preskočila u prvom od najduljih skokova na stazi;

Primjeri test podataka

Ulaz

1
5

Izlaz

1
1
5

Ulaz

10
100
13
1003
7000
5000
1004
101
7
8
6000

Izlaz

7
2
7