Az S. 81. feladat (2013. május)

S. 81. Egy házat szeretnénk felépíteni, ahol ismertek a munkafázisok (pl. üvegezés, villany bevezetése, vakolás stb.). Az építési munkákról ismert, hogy egyes feladatok elkezdése után legalább mennyi időnek kell eltelnie, amikortól bizonyos más feladatokat elkezdhetünk (pl. a villany bevezetése előtt meg kell építeni a falakat, ami x nap). Egyszerre akár több munkafázison is dolgozhatunk. A ház építéséhez bérelnünk kell eszközöket az utolsónak elkezdett munkafázis első napjáig, mivel feltehetjük, hogy a legutolsó munkafázis egy nap alatt befejezhető. Tehát ha a T. napon kezdünk el utoljára munkafázist, akkor összesen T^.P forint bérleti díjat kell fizetni. Az alapanyagok megvásárlása következtében minden munkafázis további költségeket jelent. A mostani feladatban úgy tekintjük, hogy az alapanyagok ára monoton csökken (azaz későbbi időpontban sosem lesz nagyobb, mint egy korábbi esetén lenne), és intervallumonként konstans. (Vagyis pl. 1-10. napig 30 forint, 11-20. napig 20, utána 21-40. napig 15 forint.)

Írjunk programot, amely a feladatok egymásra épülése, a P bérleti díj, illetve az egyes feladatokhoz szükséges intervallumonkénti alapanyagárak ismeretében megadja, hogy minimum mennyi pénzbe kerül a ház fölépítése, ha a lehető legügyesebben ütemezzük az egyes feladatok elkezdését.

A standard bemenet első sorában található a feladatok N, illetve az egymásra épülések E száma, valamint a P bérleti díj (, , 0P1000) szóközökkel elválasztva. A következő E sor mindegyikében három szám található, példaként (a_i,b_i,c_i), amelyek egymásra épüléseket írnak le: az a_i sorszámú munka megkezdése után c_i nappal lehet elkezdeni a b_i sorszámú munkát (1iE). A következő N sor az egy-egy munkához szükséges alapanyagok árainak alakulását tartalmazza a következőképpen: az első szám K (1K100), és ezután K darab egymáshoz illeszkedő intervallum leírása következik két-két számmal (f_j,v_j), melyek jelentése: az intervallumon f_j forintba kerül megvenni az alapanyagokat az adott munkához, és a v_j-edik nap az intervallum utolsó napja (azaz amikor még f_j forintba kerül a vásárlás) (0f_j1000, 1v_j10⁹). Az első intervallum az 1. napon indul, a továbbiak pedig mindig az előző intervallum vége utáni napon kezdődnek (1jK).

A standard kimenet egyetlen sorába írjuk ki a ház fölépítésének minimális költségét.

Feltehetjük, hogy az egymásra épülésekből nem következik ellentmondás, vagyis a ház mindenképpen felépíthető. Az egyes feladatokhoz szükséges alapanyagokat a feladat elkezdésének napján kell megvennünk. Az utolsó árintervallumok minden feladatnál ugyanazon a D. napon végződnek (1D10⁹). Az építkezést leghamarabb az 1. napon kezdhetjük, és be kell fejeznünk legkésőbb a D. napon.

Magyarázat a példához: Egy optimális építési tervben pl. a következőek lehetnének az elkezdési idők: 1, 2, 4, 8 vagy 1, 2, 3, 8. Ekkor az alapanyag beszerzések költsége 3+2+3+3=11, és ehhez jön még 8 Ft bérleti díj, vagyis az összköltség 19. (Ha az elkezdési idők pl. 1, 2, 3, 7 lennének, akkor az összköltség 3+2+3+10+7=25 lenne.)

Értékelés: 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 maximális 9 pont, ha bármilyen, a feltételeknek megfelelő tesztesetet képes megoldani 1 mp futásidőkorláton belül. A megoldásra részpontszám kapható, ha a program csak a maximális bemeneti számoknál nagyságrendekkel kisebb tesztesetekre tud lefutni időben (pl. kisebb N, E, v_j, vagy K).

Beküldendő egy tömörített s81.zip állományban a program forráskódja (s81.pas, s81.cpp, ...) az .exe és más, a fordító által generált állományok nélkül, a program rövid dokumentációja (s81.txt, s81.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ó.

(10 pont)

A beküldési határidő 2013. június 10-én LEJÁRT.

Ha az alapanyagárak nem változnának, akkor ez a feladat a jól ismert kritkus út probléma lenne: adottak részmunkák egymásra épülései időközökkel, és számítsuk ki, hogy mikor végezhetünk a leghamarabb az összes munkával (hiszen a bérleti díjból származó kiadás az idő előrehaladtával nő).

Először gondoljuk végig a kritikus út probléma megoldását. Adódik, hogy a probléma modellezésére egy élsúlyozott, irányított gráfot használjunk: az u->v él jelentse azt, hogy az u munka elkezdése után az él súlyának megfelelő időt kell várni a v munka elkezdése előtt. Az egyes munkák leghamarabbi lehetséges elkezdési idejére adható egy rekurzív összefüggés, amelyben a befutó élek másik végpontjainak leghamarabbi elkezdési idejei, és az éleken lévő késleltetések szerepelnek: tekintsük azokat a munkákat, amelyekre épül az aktuális (x) munka, és adjuk hozzá mindegyiknek a minimális elkezdési idejéhez azt az időt, amennyinek el kell telnie az x elkezdéséig, majd ezeknek vegyük a maximumát. Ezt implementálhatjuk memorizáló rekurzióval (azaz egy olyan rekurzív függvénnyel, ami csak akkor számítja ki a paraméterül kapott csúcsra a leghamarabbi kezdési időt, ha még nem számította ki korábban), vagy kiszámolhatjuk az értékeket rekurzív függvény nélkül is, ha mindig figyelünk arra, hogy egy olyan csúcsnak számoljuk ki az értékét, amelybe befutó összes él másik végpontjának az értékét már kiszámoltuk (ehhez pl. számon tarthatjuk minden csúcsra, hogy hány kiszámolatlan közvetlen őse van, és a nullát elért számlálójú csúcsokat egy sorba tehetjük). Ennek az algoritmusnak a futásideje a csúcsok plusz élek számával arányos.

Most térjünk vissza az eredeti feladathoz. Itt az alapanyagárak csökkennek, ami arra késztet bennünket, hogy minél később kezdjük el az egyes munkákat. Ha az összes részmunka minden lehetséges elkezdési idejeinek minden kombinációját kipróbálnánk, az nyilvánvalóan nagyon lassú programot eredményezne. Azonban vegyük észre, hogy ha rögzítjük a teljes munka elkészülési idejét, akkor megoldhatjuk az alapanyagárak minimalizálását a kritikus út probléma megoldási algoritmusával, hiszen ekkor minden munkát a lehető legkésőbb érdemes elkezdenünk (hiszen az alapanyagárak monoton csökkennek) annak figyelembe vételével, hogy nem dolgozhatunk a rögzített nap után. Ez pont a kritikus út probléma időbeli fordítottja: olyan, mintha a rögzített időpont lenne a 0 pont (az eredeti kritikus út problémában ugyebár a 0 időpont előtt nem dolgozhatunk), és az élek fordítva lennének.

A határokat megnézve kiderül, még mindig nem elég gyors az algoritmusunk: Az árintervallumok lehetnek akár 10⁹ nagyságrendűek is, tehát nem próbálhatjuk ki az összes lehetséges rögzítését a teljes munka elkészülési idejének. Viszont most kihasználhatjuk azt a tényt, hogy az alapanyagárak szakaszonként konstans függvények: ha elképzelünk egy munkatervet az egész munkára, majd ezt elkezdjük időben mozgatni, akkor csak olyankor változhat az alapanyagok beszerzési ára, amikor valamelyik munka éppen egy intervallumhatárhoz ér. Ez alapján a következő megoldás adódik: számoljuk ki a lehető leghamarabbi munkabefejezést, és a hozzá tartozó ütemezést, majd toljuk el az egész munkatervet minden lépésnél pont annyival, hogy már megváltozzon az össz alapanyagár, és közben végezzünk minimumkeresést az össz alapanyagár és a bérlési költség összegére. (A kezdeti munkatervünket a fentebbi fordított kritikus út algoritmussal számítjuk ki, vagyis az egyes munkák a lehető legkésőbbre kerülnek.)

A valóban hatékony implementáció eléréséhez még alakítani kell a fentebbi algoritmuson: nem szeretnénk minden lépésben az egész munkaterv módosításával tölteni az időt, továbbá a legközelebbi intervallumhatár megkeresésére is kell egy hatékony módszer. Valójában két dolog számon tartására van szükségünk: az aktuális eltolás (a 0 ponthoz képest), és az aktuális eltoláshoz tartozó össz alapanyagár. Ha először kiszámolunk egy kezdeti munkatervet, akkor már minden egyes munka összes intervallumhatárára kiszámolhatjuk, hogy mikor érjük el, hiszen csak a munkatervbeli eltolását kell alkalmaznunk. Így kapjuk alapanyagár-változási eseményeknek egy gyűjteményét. Ha ezt rendezzük a bekövetkezési idő szerint, akkor már csak ezeken kell végiglépegetnünk, és közben minimumkeresést csinálnunk az aktuális árra. Ennek az algoritmusnak a futásideje O(NKlog (NK)), mivel az események (intervallumhatárok) rendezése a leglassabb művelet.

Mintamegoldás: S81.cpp

Statisztika:

2 dolgozat érkezett.
10 pontot kapott:	Szabó 928 Attila.
4 pontot kapott:	1 versenyző.

A KöMaL 2013. májusi informatika feladatai