Državno natjecanje 2016. / Osnovna škola (8. razred) - 2. zadatak

Na izletu s roditeljima u jednom europskom gradu, gledajući kroz prozor hotela, Mirko čita brojeve s gradskih autobusa i stalno govori: “Ovo mi je dobar broj!

Ovo mi je dobar broj!” Kad su ga roditelji pitali kako to da on ima toliko dobrih brojeva, Mirko je objasnio da je njemu dobar svaki broj koji se od njegovog sretnog broja razlikuje za manje od K.

Primjerice, ako je Mirkov sretan broj 50 i ako je K = 10, onda su mu dobri svi brojevi od 41 do 59.

Osim toga, Mirko često mijenja svoj sretan broj tako da mu svaki broj koji pročita na gradskom autobusu bude dobar.

Primjerice, ako je Mirkov sretan broj 50 i ako je K = 10, a uskoro će proći autobusi 12 i 16, Mirko će svoj sretan broj promijeniti npr. na 15 tako da mu brojevi 12 i 16 budu dobri.

Tvoj je zadatak, znajući redoslijed prolaska N gradskih autobusa pokraj Mirkovog prozora i znajući Mirkov sretan broj S prije prolaska prvog autobusa, odrediti koliko najmanje puta Mirko mora promijeniti svoj sretan broj tako da mu svaki autobus bude dobar u trenutku prolaska.

Napomena: brojevi će u nekim test podacima biti jako veliki; pripazi na vremensko ograničenje!

ULAZNI PODATCI

U prvom retku nalazi se prirodan broj N (1 ≤ N ≤ 100 000), broj autobusa koji će proći.

U drugom retku nalaze se prirodni brojevi S i K (manji od 1 000 000) iz teksta zadatka.

U sljedećih N redaka nalaze se oznake autobusa (prirodni brojevi manji od 1 000 000), redom kojim prolaze.

IZLAZNI PODATCI

U jedini redak ispiši traženi najmanji broj promjena Mirkovog sretnog broja.

PRIMJERI TEST PODATAKA

Ulaz

4
18 7
10
45
55
65

Izlaz

3

Objašnjenje

Opis prvog test podatka: K = 7. Da bi mu autobus 10 bio dobar, Mirko odmah mora promijeniti svoj sretan broj (s broja 18) npr. na broj 10. Potom dolaze autobusi 45, 55, 65.

Mirko osigurava da su mu oni dobri tako što, primjerice, svoj sretan broj mijenja na 45 (za autobus 45) i potom na 60 (za autobuse 55 i 65).

Ulaz

11
15 5
12
14
29
32
37
53
67
63
10
7
9

Izlaz

4