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 (bi és ji), 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 xj, yj egészek megmutatják, hogy a j-edik másodpercben az xj-edik majom az yj-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
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