Az I/S. 13. feladat (2016. december)

I/S. 13. A rendőrség már hónapok óta figyel egy veszélyes bűnözőt. A megfigyelés során összesen \(\displaystyle N\) fontos helyen bukkant fel, és megfigyelték, hogy ha egy adott helyen van, akkor vagy taxival megy tovább, vagy gyalogol, viszont utóbbi esetben mindig ugyanarra. Tehát ha az \(\displaystyle i\)-edik helyről gyalog megy tovább, akkor mindig egy adott \(\displaystyle B_{i}\) helyen fog legközelebb felbukkanni.

A mai napra elég bizonyíték gyűlt össze ellene, így elhatározták, hogy letartóztatják. A kapcsolatai révén erről biztosan értesült a bűnöző, így semmiképpen sem fog taxival menni, mivel a taxisok feladhatják a rendőrségnek, vagyis gyalog fog menekülni. A rendőrök sajnos nem ismerik a bűnöző mostani helyzetét, viszont elkezdték visszanézni az \(\displaystyle N\) fontos hely biztonsági kameráit. Bíznak benne, hogy hamarosan az egyik kamera felvételein megtalálják. Addig is minket kértek meg, hogy mind az \(\displaystyle N\) helyszínre dolgozzunk ki egy ,,elfogási tervet''. Az elfogási terv az \(\displaystyle i\)-edik helyszín esetén egy olyan \(\displaystyle Q_{i}\) helyre vezényli ki a rendőröket, hogy ha az \(\displaystyle i\)-edik helyen járt a bűnöző és ezután csak gyalog haladt (a kifigyelt mintát követve), akkor akármilyen régi is a felvétel, biztosan fel fog még bukkanni a \(\displaystyle Q_{i}\) helyen. Írjunk programot, ami a megfigyelés eredménye alapján minden helyre megad egy elfogási tervet.

A standard bemenet első sora a helyek \(\displaystyle N\) számát, a következő sor pedig \(\displaystyle N\) egész számot tartalmaz, az \(\displaystyle i\)-edik szám a fent említett \(\displaystyle B_{i}\) érték.

A standard kimenet első és egyetlen sora \(\displaystyle N\) egészet tartalmazzon, az \(\displaystyle i\)-edik szám az \(\displaystyle i\)-edik pontra kidolgozott elfogási tervben szereplő \(\displaystyle Q_{i}\) hely sorszáma legyen. Több megoldás esetén bármelyik megadható.

Korlátok: \(\displaystyle 1\le N\le 10^{6}\), \(\displaystyle 1\le B_{i}\), \(\displaystyle Q_{i}\le N\). Időlimit: 0,1 mp. Memórialimit: 256 MB. A verem (stack) méretére nincs külön korlát, de a teljes memórialimitbe számít bele.

Minta:

Magyarázat: a menekülési útvonalak az alábbiak:

1-es pont: \(\displaystyle 1\to 2\to 2\to 2\to \ldots\)

2-es pont: \(\displaystyle 2\to 2\to 2\to \ldots\)

Pontozás és korlátok: a programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani a fenti korlátoknak megfelelően.

Beküldendő egy tömörített is13.zip állományban a program forráskódja és rövid dokumentációja, amely megadja, hogy a forrásállomány melyik fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2017. január 10-én LEJÁRT.

Statisztika:

16 dolgozat érkezett.
10 pontot kapott:	Gáspár Attila, Horváth Botond István, Janzer Orsolya Lili, Kiss Gergely, Nagy Nándor, Németh 123 Balázs, Noszály Áron, Szakály Marcell, Tóth 827 Balázs.
9 pontot kapott:	Busa 423 Máté.
8 pontot kapott:	1 versenyző.
5 pontot kapott:	1 versenyző.
3 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2016. decemberi informatika feladatai