Državno natjecanje 2013. / Osnovna škola (6. razred) - 3. zadatak

Vesna je velika ljubiteljica dobre glazbe i u svom vlasništvu ima N orginalnih glazbenih CD-ova.

Svaki CD je označen svojim brojem izmeñu 1 i N. CD možemo zamisliti kao krug polumjera R.

Pri tome CD-ovi mogu biti različitih polumjera jer ih je Vesna naručivala iz raznih stranih zemalja.

Vesna je odlučila složiti svoje CD-ove na CD stalke. Kako je ona vrlo uredna, pri slaganju CD-ova posebno pazi da svi budu pravilno složeni.

Neki CD je pravilno složen ako je njegov polumjer manji od polumjera CD-a koji se nalazi neposredno ispod njega ili ako je veći uz uvjet da je razlika njihovih polumjera najviše X.

Naravno, ispod CD-a na dnu stalka ne nalazi se ni jedan drugi CD tako da se za njega podrazumijeva da je pravilno složen.

Pitanje koje sada muči sve nas je koliko najmanje stalaka treba nabaviti da bismo sve CD-ove mogli pravilno složiti.

Oprez, CD-ove moramo slagati na stalke po redu, počevši od onog s najmanjom oznakom, a tijekom slaganja ih ne smijemo premještati.

ULAZNI PODATCI

U prvom retku nalazi se prirodan broj N (1 ≤ N ≤ 100), broj CD-ova i cijeli broj X (0 ≤ X ≤ 100) čije je značenje opisano u zadatku.

U sljedećih N redova nalazi se po jedan prirodan broj Ri (1 ≤ Ri ≤ 100), polumjer CD-a s oznakom i.

IZLAZNI PODATCI

prvi redak treba ispisati traženi minimalan broj stalaka iz zadatka.

PRIMJERI TEST PODATAKA

Ulaz

5 1
1
2
3
4
5

Izlaz

1

Ulaz

5 0
1
2
3
4
5

Izlaz

5

Ulaz

6 2
3
5
8
1
4
7

Izlaz

3

Objašnjenje

Pojašnjenje trećeg test primjera: Prva dva CD-a Vesna će staviti na prvi stalak jer im je razlika u polumjeru točno 2.

Treći CD morat će staviti na drugi stalak.

Četvrti i peti CD Vesna će staviti redom na prvi i drugi stalak jer su manji od CD-a na vrhu, dok će posljednji CD morati staviti na odvojeni stalak. To su ukupno 3 stalka