Školsko natjecanje iz informatike 2018. / Prva podskupina (1. i 2. razred) - 3. zadatak

Dwight Schrute napokon je postao šef podružnice Dunder Mifflina1 . Nakon što je osobno proveo detaljnu istragu o svih svojih \(N\) zaposlenika, Dwight ih je odlučio ocijeniti. Svakom zaposleniku dodijelio je broj od 1 do \(N\), tako da broj 1 označava najmanju, a broj N najvišu ocjenu. Dwight voli rangiranje pa dva zaposlenika nikada nemaju istu ocjenu, tj. svaka ocjena 1, 2, …, \(N\) dodijeljena je točno jednom zaposleniku.

Kada neki zaposlenik (ocijenjen s \(X\)) napravi pogrešku, Dwight ga kažnjava tako da najprije svim niže ocijenjenim zaposlenicima (s ocjenama manjima od \(X\)) poveća ocjenu za 1, a potom zaposleniku koji je pogriješio dodijeli najnižu ocjenu 1.

Dwightova djevojka Angela odlučila je podružnicom upravljati iz sjene te je Dwightu pokazala vlastite ocjene zaposlenika. Dwight zna da ne može odjednom promijeniti ocjene kako Angela želi, ali ipak je odlučio nizom kažnjavanja stvarnih ili izmišljenih pogrešaka zaposlenika doći do traženih ocjena. Pomozite Dwightu i odredite najmanji broj kažnjavanja potreban da trenutačne ocjene svojih zaposlenika promijeni u ocjene koje je zamislila Angela. Preciznije, odredite zaposlenike koje treba kazniti.

U prvom retku nalazi se prirodan broj \(N\) \((2 \leq N \leq 10)\), broj zaposlenika. U drugom retku nalazi se niz od N prirodnih brojeva iz skupa {1, 2, …, \(N\)}, trenutačne ocjene zaposlenika. Zaposlenici su navedeni fiksnim redoslijedom od najstarijeg do najmlađeg. U drugom retku nalazi se niz od N prirodnih brojeva iz skupa {1, 2, …, \(N\)}, ciljane ocjene istih zaposlenika. I u prvom i u drugom nizu svaka se ocjena javlja točno jednom te se nizovi ne podudaraju.

Ispišite onoliko redaka koliko je (minimalno) potrebno kažnjavanja. U pojedini redak ispišite redni broj (iz zadanog poretka od najstarijeg do najmlađeg) zaposlenika koji se kažnjava. Može se pokazati da je rješenje jedinstveno, tj. postoji samo jedan optimalan redoslijed kažnjavanja.

Ulaz

3
3 1 2
3 2 1

Izlaz

3

Objašnjenje

Kažnjavanjem trećeg zaposlenika njegova ocjena iz 2 postaje 1, a ocjena drugog zaposlenika povećava se iz 1 u 2.

Ulaz

4
1 3 4 2
1 4 2 3

Izlaz

3
1

Objašnjenje

(1, 3, 4, 2) -> (2, 4, 1, 3) -> (1, 4, 2, 3).