Državno natjecanje 2017. / Osnovna škola (7. razred) - 3. zadatak

Prilikom ulaska u banku, klijent (korisnik banke) iz aparata izvlači broj koji određuje kada će doći na red. Klijent potom čeka da se njegov broj prikaže na ekranu.

Aparat radi tako da redom izbacuje prirodne brojeve 1, 2, 3, …, K i nakon što izbaci najveći broj (K), nastavlja ponovno od broja 1.

Na početku dana aparat ne mora početi od broja 1.

Jednoga dana banka je opljačkana.

U trenutku pljačke u banci je bilo N svjedoka, klijenata banke.

U svrhu istrage, policija želi odrediti redoslijed kojim su ti klijenti ušli u banku.

Neki od njih sačuvali su ili zapamtili broj izvučen iz aparata na ulazu u banku, a neki su svoj broj u međuvremenu izgubili ili zaboravili.

Nije poznato koji je broj izvučen prvi ili posljednji.

Tvoj je zadatak pomoći policiji i pronaći neki poredak u kojem su svjedoci mogli ući u banku, koristeći poznate informacije o izvučenim brojevima.

ULAZNI PODATCI

U prvom retku nalaze se prirodni brojevi N i K iz teksta zadatka (1 < N, K < 100 000). Klijenti (svjedoci) označeni su brojevima 1, 2, ..., N.

U drugom retku nalazi se N cijelih brojeva iz intervala [0, K], a opisuju brojeve koje su pri ulazu u banku izvukli klijenti 1, 2, ..., N. Ako je m-ti broj jednak 0, to znači da klijent m nije sačuvao svoj broj.

IZLAZNI PODATCI

U jednom retku ispiši niz brojeva iz skupa {1, 2, …, N} koji predstavlja neki mogući redoslijed ulaska danih N ljudi u banku. Ako nema rješenja, ispiši samo broj 0.

PRIMJERI TEST PODATAKA

Ulaz

3 7
7 0 5

Izlaz

3 2 1

Objašnjenje

Opis prvog test podatka: Klijent 3 ulazi i izvlači broj 5, klijent 2 ulazi i izvlači broj 6, klijent 1 ulazi i izvlači broj 7.

Ulaz

3 7
2 0 5

Izlaz

0

Ulaz

5 3
0 3 2 2 0

Izlaz

4 2 1 3 5

Objašnjenje

Opis trećeg test podatka: Klijent 4 ulazi i izvlači broj 2, klijent 2 ulazi i izvlači broj 3, klijent 1 ulazi i izvlači broj 1, klijent 3 ulazi i izvlači broj 2, klijent 5 ulazi i izvlači broj 3.

Ovo nije jedino moguće rješenje za ovaj primjer.