Az S. 74. feladat (2012. október)

S. 74. Atommeghajtású űrhajónkkal szeretnénk eljutni egy másik csillagrendszerbe úgy, hogy a lehető legtöbb titánnal érkezzünk meg. Van egy térképünk az ismert csillagrendszerekről, melyek között kizárólag egyirányú féregjáratokon tudunk közlekedni. A féregjáratrendszer jelenlegi állapotában teljesül minden csillagrendszerre, hogy ha kilépünk belőle, akkor biztosan nem tudunk visszajutni.

Minden csillagrendszerről tudjuk, hogy mennyi uránt (melyet üzemanyagként használunk), illetve titánt tudunk bányászni, ha meglátogatjuk. Az urán tárolása körülményes, ezért csak meghatározott mennyiséget tudunk belőle raktározni. Minden féregjáratról tudjuk, hogy mennyi uránt fogyasztunk az áthaladás közben. Szerencsére bármely csillagrendszerben feltölthetjük uránkészletünket egy egységnyi titánért. Kezdetben tele van az üzemanyagtartályunk, és nincs titánunk.

Írjunk programot, amely a standard inputról beolvassa a térképet, valamint az induló- és a célcsillagrendszer sorszámát, és megadja, hogy legföljebb mennyi titánnal érhetünk el a célba, továbbá az ehhez szükséges útvonalat is.

Bemenet: A standard input első sorában öt szám található, szóközökkel elválasztva: a csillagrendszerek () száma, a féregjáratok () száma, az induló- és a célcsillagrendszer sorszáma (a csillagrendszereket 1-től N-ig sorszámozzuk), valamint az üzemanyagtartályunk () kapacitása.

A következő N sor rendre az -edik csillagrendszert írja le két, szóközzel elválasztott egész számmal, melyek megadják a bányászható titán és urán mennyiségét (). Az utolsó M sor rendre az -edik féregjáratot írja le három egész számmal, melyek a járat kezdő- és célcsillagrendszerének sorszáma és az áthaladáshoz szükséges urán mennyisége ().

Feltehetjük, hogy a kezdő- és célcsillagrendszer nem esik egybe, valamint, hogy nincs két olyan féregjárat, melyek ugyanazt a két csillagrendszert kötik össze, továbbá, hogy a féregjáratok kezdő- és végpontja sem esik egybe.

Kimenet: A program írja ki a standard kimenet első sorába, hogy maximum mennyi titánnal érkezhetünk meg célunkhoz. A második sorba írjunk ki egy ehhez szükséges útvonalat is, a következő formában: az első szám legyen az útvonalban szereplő csillagrendszerek száma (beleértve a kezdő- és célcsillagrendszert), aztán az úton szereplő csillagrendszerek sorszámának felsorolása következzen.

Amennyiben nem juthatunk el a célig, akkor a standard kimenet egyetlen sorába a -1 szám kerüljön.

Példák:

Pontozás: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 2 pontot ér. A programra akkor kapható meg a maximális 8 pont, ha bármilyen, a feltételeknek megfelelő tesztesetet képes megoldani a 3 mp futási időlimiten belül. Kapható részpontszám, ha a program csak kisebb tesztesetekre tud lefutni időben, továbbá akkor is, ha a program csak olyan teszteseteket tud megoldani, amelyeknél a féregjáratokon való áthaladáshoz szükséges üzemanyag mennyisége mindig 0.

Beküldendő egy tömörített s74.zip állományban a program forráskódja (s74.pas, s74.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 (s74.txt, s74.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrás mely fejlesztői környezetben fordítható.

Példa be- és kimenetek: s74.zip

Danner Gábor ötlete alapján

(10 pont)

A beküldési határidő 2012. november 12-én LEJÁRT.

Általánosságban elmondható a beérkezett megoldásokról, hogy nagyon sok bennük a hiba. Egyetlen tökéletes megoldás sem érkezett. Egy olyan versenyen, ahol csak a kimeneteket nézik meg (pl. OKTV), sokan még több pontot vesztettek volna. A weboldalra általában szoktak felkerülni tesztadatok a feladatokhoz, amelyekre érdemes letesztelni a programjaitokat beküldés előtt. Példaképpen néhány olyan buktató, amely szerepelt a bemenetekben: nem 1-es kezdőcsúcs, sallang csúcsok, használhatatlan él, bányászható kezdő- és célrendszer, fölöslegesen sok uránium, vásárlásra kényszerítés, "hitelezést" megengedő bug esetén eltérő optimum.

A bemenetet felfoghatjuk egy körmentes, irányított gráfként, amelyben a csúcsok a csillagrendszerek, és az élek a féregjáratok.

Backtrack

A feladatot megpróbálhatjuk egy olyan backtrackkel megoldani, amely minden lehetséges útvonalat végignéz, és ezek közül kiválasztja a legjobbat. Ez a megoldás nem fut le időben a nagyobb tesztesetekre, hiszen előfordulhat, hogy nagyon sokféle úton juthatunk el a célhoz. (n-nel exponenciálisan arányos futásidejű) Ennek az algoritmusnak a hibátlan megvalósításával 6 pontot lehetett szerezni.

S74Backtrack.cpp

Dinamikus programozás rekurzióval és memorizálással

Először is vegyük észre, hogy ha egy adott csúcsba vezető két különböző útvonal olyan, hogy az elsővel kevesebb titánnal érkezünk meg, mint a másodikkal, akkor az urán mennyiségétől függetlenül biztosan a második a jobb. Más szóval egy olyan teljes rendezés adható az adott végpontú útvonalak között, amely egyszerűen egy kétkulcsos rendezés a végpontban lévő titán- és uránmennyiségre. (Hiszen egy egységnyi titánért bármikor feltölthetjük a tankunkat.) Ezt figyelembe véve adódik egy dinamikus programozásos megoldás: jelöljük opt[i]-vel az i. csúcsba vezető optimális útvonal végén a titán és uránmennyiségünket. Ekkor opt[i] értéke csak azon csúcsok opt értékétől fog függeni, amelyekből közvetlenül vezet él i-be. Két lehetőségünk van a fenti ötletből konkrétabb algoritmust gyártani:

1. Az opt-ra felírt rekurzív összefüggést közvetlenül implementáljuk egy rekurzív függvénnyel. Ehhez mindenképpen használnunk kell memorizálást, ami azt jelenti, hogy a függvény első dolga ellenőrizni, hogy nem számolta-e már ki az opt értéket a paraméterben kapott csúcsra, és ha igen, akkor nem számolja ki újra, hanem csak visszatér a már korábban kiszámolt értékkel. (Memoization oldala a Wikipedián) (Memorizálás nélkül ekvivalens lenne ez a megoldás a fentebbi backtrackkel: az útvonalak számával arányos ideig futna.)

S74DP.cpp

2. Csinálunk először egy topologikus rendezést a csúcsokra, azaz olyan sorrendbe tesszük őket, hogy nem vezet későbbiből korábbiba él (a körmentesség miatt ilyen sorrend biztosan van). Ezt elvégezhetjük egy olyan mélységi bejárással, amelynek a rekurzív függvénye a visszatéréskor hozzáfűzi egy lista végére az aktuális csúcsot. Végiggondolható, hogy ha végül megfordítjuk ezt a listát, akkor valóban egy topologikus sorrendet kapunk (ld. pl. a Topologikus rendezés oldala a Wikipedián). Ezután ebben a sorrendben meghatározhatjuk az opt értékeket, mivel minden olyan csúcs már "készen van", amelyből vezet él az aktuális csúcsba.

Statisztika:

11 dolgozat érkezett.
9 pontot kapott:	Szabó 928 Attila.
8 pontot kapott:	2 versenyző.
6 pontot kapott:	1 versenyző.
5 pontot kapott:	2 versenyző.
3 pontot kapott:	3 versenyző.
2 pontot kapott:	2 versenyző.

A KöMaL 2012. októberi informatika feladatai