Az S. 86. feladat (2014. január)

S. 86. Egy parkban azt látjuk, hogy N majom közül az 1-es számú egy nagyon nagy fa egyik ágába kapaszkodik a farkával. A majmok a kezükkel kapcsolódhatnak más majmokhoz úgy, hogy egy majom egy másik lábát fogja. Így tarthatnak más majmokat azáltal, hogy beléjük kapaszkodnak, vagy úgy, hogy beléjük kapaszkodnak más majmok. Egy majom lábába bárhány majom kapaszkodhat. Szeretnénk végezni egy M másodpercig tartó vizsgálatot, amelynél minden másodpercben egy majom szabaddá teszi adott kezét, vagyis elengedi egy másik majom lábát, ha eddig fogta azt. A program számítsa ki, hogy mikor esnek le az egyes majmok a földre. Egy majom akkor esik le, ha az 1-es számú majom nem tartja közvetett, vagy közvetlen módon.

A standard bemenet első sorában a majmok száma és a vizsgálat ideje másodperc található, a következő N sor mindegyikében két szám (b_i és j_i), amely megadja, hogy az i-edik majom a bal és a jobb kezével hányadik majomba kapaszkodik. Amennyiben valamelyik szám -1, az azt jelenti, hogy azzal a kezével senkibe sem kapaszkodik, azzal a kezével senkit sem tart. A standard bemenet következő M sorában az x_j, y_j egészek megmutatják, hogy a j-edik másodpercben az x_j-edik majom az y_j-edik kezével elengedi a fogást (1. kéz a bal, 2. kéz a jobb). A program írja a standard output N sorába a majmok földet érésének idejét. Az i-edik sorba az i-edik majom földet érésének ideje kerüljön, és -1, ha nem ér földet a vizsgált időintervallum végéig.

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 beolvasástól számított 0.05 mp futásidőkorláton belül.

Részpontszámok a következőkre kaphatóak:

- a program N100-ra megoldást ad;

- a program N5000-re megoldást ad;

- a program -re megoldást ad.

Beküldendő egy tömörített s86.zip állományban a program forráskódja (s86.pas, s86.cpp, ...) az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja (s86.txt, s86.pdf, ...), amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(10 pont)

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

Mintamegoldásnak Weisz Ambrus és Makk László megoldását tesszük közzé. Az alapötlet az, hogy időben visszafelé nézzük az eseményeket. Innentől egy szélességi bejárás megoldja. main.cpp

S86megoldas.txt

s86.zip

Statisztika:

14 dolgozat érkezett.
10 pontot kapott:	Makk László, Weisz Ambrus.
8 pontot kapott:	1 versenyző.
7 pontot kapott:	3 versenyző.
5 pontot kapott:	1 versenyző.
4 pontot kapott:	2 versenyző.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2014. januári informatika feladatai