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

Mirko u svojoj sobi ima policu s 500 mjesta koja je označio brojevima od 1 do 500. Na svako mjesto stavio je po jedan kamen koji je sakupljao tijekom godina sudjelovanja na natjecanju u Primoštenu.

Odabrao je N od tih 500 kamenja i na svaki od njih zapisao jedan jedinstveni prirodan broj između 1 i N. Broj 1 je napisao na kamen koji se na polici nalazi na mjestu s oznakom T1, broj 2 je napisao na kamen na mjestu s oznakom T2 i tako sve do broja N kojeg je zapisao na kamen na mjestu TN. Mirko je pazio da se na jedan kamen ne zapišu dva broja.

U trenutku dosade, odlučio je preslagivati kamenje na polici uz tvoju pomoć. Jedno preslagivanje uključuje zamjenu nekoliko uzastopnih kamenja s istim brojem uzastopnih kamenja na drugom mjestu. Preslagivanje se definira na sljedeći način:

1. Na polici pronađi najdesniji kamen na kojem piše broj. Odaberi taj kamen i odaberi još X kamenja neposredno lijevo od njega, bez obzira piše li na njima neki broj ili ne.
2. Krenuvši od najljevijeg kamena odabranog u prošlom koraku, u smjeru prema kamenu 1 (prema lijevo), pronađi prvih sljedećih uzastopnih (X+1) kamenja na kojima ne piše prirodan broj. Tih (X+1) kamenja zamijeni s kamenjem odabranim u točki 1. zadržavajući njihov originalni poredak gledajući s lijeva na desno. Vrijednost X-a bit će takva da će se preslagivanje uvijek moći provesti.

Mirko je u jednom danu odradio K preslagivanja. Za svako preslagivanje bit će zadana vrijednost X koja može biti i nula što znači da će se zamjenjivati samo najdesniji kamen sa zapisanim brojem na sebi i prvi kamen lijevo od njega na kojem ne piše broj.

Ispiši prirodne brojeve od 1 do N, onim redoslijedom kojim se pojavljuju na kamenju, s lijeva na desno, nakon K preslagivanja.

ULAZNI PODATCI

U prvom retku nalazi se prirodan broj N (1 ≤ N ≤ 50), broj iz teksta zadatka.

U i-tom od sljedećih N redaka nalazi se prirodan broj Ti (1 ≤ Ti ≤ 500), oznaka mjesta na polici na kojem je Mirko na kamen napisao broj i.

U sljedećem retku nalazi se prirodan broj K (1 ≤ K ≤ 200), broj iz teksta zadatka.

U sljedećih K redaka nalazi se po jedan cijeli broj Xi (0 ≤ Xi < N), vrijednost iz teksta zadatka za svako od K preslagivanja.

IZLAZNI PODATCI

U N redaka treba ispisati prvih N prirodnih brojeva iz teksta zadatka