Državno natjecanje 2014. / Osnovna škola (7. razred) - 2. zadatak

Na izlazu s autoceste nalazi se naplatna kućica. Na njoj je postavljena kamera.

Vidokrug kamere (prostor koji snima) je od X-tog do Y-tog metra ceste ispred kućice (vidi sliku 1).

Stvorila se gužva. U redu za naplatu ispred kućice čeka N vozila.

Naplata traje jednu minutu po vozilu. Kada prvo vozilo iz reda prođe naplatu, sva ostala odmah se pomaknu naprijed zadržavajući isti poredak.

Poznate su duljine svih N vozila.

Između njih nema razmaka. Nadzornik autoceste uključio je kameru i prati stanje u redu.

U redu se mogu naći i vozila hitne pomoći.

Prepoznajemo ih po tome što su od svih vozila jedina duljine točno 5 metara. Posebna situacija nastaje kada nadzornik uoči hitnu.

Ona tada odmah izlazi s autoceste bez naplate, a vozila iza nje pomiču se naprijed (sve se ovo dogodi u nula sekundi).

Nadzornik hitnu može uočiti na dva načina:

1. Na kameri - Ako je hitna (barem jednim svojim dijelom) u nekom trenutku u vidokrugu kamere (bilo prilikom pomicanja vozila, bilo da se u njemu već nalazi).
2. Na naplatnoj kućici - Ako je hitna u nekom trenutku prva u redu za naplatu. Do ovog slučaja dolazi samo kada nadzornik hitnu ne uoči na prvi način.

To se događa kada se hitna već na početku nalazi blizu kućice, unutar prvih X metara, što je izvan vidokruga kamere.

Srećom, hitna će se pojaviti u samo nekim test podacima (vidi dio Bodovanje).

Nadzorniku je potreban program koji će odrediti broj vozila koji se barem jednim dijelom vide na kameri.

Ispiši traženi broj vozila za svaku minutu, dok god postoji neko vozilo u redu.

ULAZNI PODATCI

U prvom retku nalaze se dva cijela broja X i Y (0 ≤ X < Y ≤ 50), početni i završni metar između kojih kamera snima.

U drugom retku nalazi se prirodan broj N (1 ≤ N ≤ 20), broj vozila u redu.

U sljedećem retku nalazi se N prirodnih brojeva Ai (1 ≤ Ai ≤ 50), duljine vozila u metrima.

IZLAZNI PODATCI

U i-ti redak izlaza ispiši koliko se vozila barem jednim dijelom vidi na kameri tijekom i-te minute, tj. u prvi redak tijekom prve minute, u drugi redak tijekom druge minute, itd.

PRIMJERI TEST PODATAKA

Ulaz

0 5
3
3 3 2

Izlaz

2
2
1

Ulaz

1 6
5
1 2 3 1 1

Izlaz

2
3
3
1
0

Objašnjenje

Opis drugog test primjera: Za pojašnjenje vidi niz slika u nastavku.

Ulaz

8 11
7
3 5 2 5 3 5 7

Izlaz

2
1
1
0

Objašnjenje

Opis trećeg test primjera: Odmah na početku nadzornik na kameri uočava drugu hitnu (četvrto vozilo u test primjeru), dok prvu hitnu još ne vidi (drugo vozilo u test primjeru).

Druga hitna odmah izlazi s autoceste i u redu ostaju vozila: [3 5 2 3 5 7].

Tijekom prve minute na kameri se vide dva vozila, masno otisnuta.

Nakon naplate u redu ostaju vozila: [5 2 3 5 7].

Nadzornik odmah uočava obje hitne: prvu na naplatnoj kućici, a drugu na kameri.

One odmah izlaze s autoceste i u redu ostaju vozila: [2 3 7].

Tijekom druge minute na kameri se vidi jedno vozilo, masno otisnuto.

Nakon naplate u redu ostaju vozila: [3 7].

Tijekom treće minute na kameri se vidi jedno vozilo, masno otisnuto. Nakon te naplate u redu ostaje samo jedno vozilo: [7].

Tijekom četvrte minute na kameri se ne vidi nijedno vozilo.