Državno natjecanje 2012. / Osnovna škola (5. razred) - 3. zadatak

Državno natjecanje 2012. / Osnovna škola (6. razred) - 2. zadatak

Poštar Joža se teško nosi s izazovima digitalnog doba.

Zbog maila, chata i sms-ova sve je manje pisama koje Joža nosi u svojoj torbi.

U ovim teškim vremenima za poštare, Joža i dalje svaki dan kruži po svom kvartu i raznosi ono malo pisama što još ima.

Njegov kvart je kružnog oblika s N kuća poredanih u krug i označenih kućnim brojevima od 1 do N (slika 1).

Između kuća Joža se kreće na svom službenom motociklu ili ide pješice, a kretati se smije samo u smjeru suprotnom od smjera kazaljke na satu.

Zbog nekih čudnih pravila Europske unije, Joža mora koristiti motocikl kada je sljedeća kuća koju planira posjetiti od trenutne kuće gdje se nalazi udaljena više ili jednako od 3 kućna mjesta.

Npr. od kuće s kućnim brojem „2“ do „6“ su četiri kućna mjesta, a od kuće s kućnim brojem „N-1“ do 2 su tri kućna mjesta.

U ostalim slučajevima, Joža mora ići pješice gurajući ugašen motocikl pored sebe.

Isto tako, ako u trenutku posjeta nekoj kući motocikl radi, on ga tada mora ugasiti.

Joža u jutro u zgradi pošte dobije popis kućnih brojeva onih kuća koje danas mora posjetiti.

Kako više voli šetnje, Joža obilazak zadanih kuća želi složiti tako da broj paljenja motocikla bude minimalan.

Zato on sam bira od koje će kuće krenuti u obilazak (ta kuća treba biti s popisa) i kojim će redoslijedom posjetiti zadane kuće.

Od zgrade pošte do odabrane početne kuće te od zadnje kuće koju obiđe natrag do pošte, Jožu i njegov ugašen motocikl prevozi poštin autobus.

Ponekad, poštin autobus Jožu preveze samo do kuće s kućnim brojem „1“ ne ostavljajući mu tako mogućnost izbora polazne kuće (izbor redoslijeda je još uvijek njegov).

Napiši program koji na osnovu popisa kućnih brojeva koje Joža mora posjetiti, ispisuje kućni broj one kuće od koje Joža kreće u obilazak te minimalan broj paljenja motora tijekom obilaska svih kuća s popisa.

Ako ima više kuća od kojih se može krenuti u obilazak, tada treba ispisati onu s najmanjim kućnim brojem.

ULAZNI PODATCI

cijeli broj 0 ili 1, oznaka vozi li (1) autobus ili ne vozi (0) samo do kućnog broja „1“;

cijeli broj N ( 1 ≤ N ≤ 50 ), broj kuća u kvartu;

prirodan broj M ( 1 ≤ M ≤ N ), broj kuća koje Joža mora posjetiti;

niz od M prirodnih brojeva X ( 1 ≤ X ≤ N ), popis kućnih brojeva koje Joža mora posjetiti.

IZLAZNI PODATCI

prirodan broj koji predstavlja kućni broj od kojeg Joža kreće u obilazak;

cijeli broj koji predstavlja minimalan broj paljenja motora pri obilasku zadanih kuća.

Napomena: U 50% test podataka, prvi ulazni podatak će obavezno biti 1.

PRIMJERI TEST PODATAKA

Ulaz

1
20
4
7
15
2
5

Izlaz

1
2

Objašnjenje

Zbog jedinice na početku, autobus je Jožu dovezao do kućnog broja „1“ te on odatle mora krenuti u obilazak.

Da bi postigao optimalni obilazak, Joža prvo posjeti kb 2, zatim kb 5 i na kraju kb-eve 7 i 15.

Motor je palio na potezu 2-5 i 7-15.

Ulaz

0
20
4
12
8
6
16

Izlaz

6
2