 |
Az S. 77. feladat (2013. január) |
S. 77. Egy robot útját kell megterveznünk egy akadálypályán úgy, hogy minél hamarabb érje el a célvonalat. A célvonal az x tengely, az akadályok pedig ezzel párhuzamos szakaszok, melyeken a robot nem képes áthaladni. (A szakaszokat ideálisnak tekintjük olyan értelemben, hogy az y tengely irányában 0 a kiterjedésük.) A robot csak a tengelyekkel párhuzamosan tud mozogni. Írjunk programot, amely az akadályok végpontjai és a robot kezdeti pozíciója alapján megadja, hogy milyen hosszú a legrövidebb út, amelyen a robot elérheti a célt.
Bemenet: A standard input első sorában az akadályok száma található (), a másodikban a robot kezdeti pozíciójának x és y koordinátája egy szóközzel elválasztva. A következő N sor leírja egy-egy akadály helyét három, szóközzel elválasztott számmal, melyek közül az első megadja az y koordinátáját, a következő kettő pedig a két végpontjának x koordinátáit. Mindegyik koordináta 1000000-nál kisebb pozitív egész szám. Az akadályok nem érintkeznek egymással, továbbá a hosszuk nem 0.
Kimenet: A standard output egyetlen sorába írjuk ki a legrövidebb út hosszát.
Példák:
Értékelé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 3 mp futásidőkorláton belül. A megoldásra részpontszám kapható, ha a program csak kisebb tesztesetekre tud lefutni időben, pl. ha a program csak olyan bemeneteket tud megoldani, amelyeknél a koordináták 0 és 100 közötti számok.
Beküldendő egy tömörített s77.zip állományban a program forráskódja (s77.pas, s77.cpp, ...) az .exe és más, a fordító által generált állományok nélkül, a program rövid dokumentációja (s77.txt, s77.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ó.
Gyebnár Gábor ötlete nyomán
Mintabemenetek: Tesztek.zip
(10 pont)
A beküldési határidő 2013. február 11-én LEJÁRT.
Egy kisebb tesztesetekre működő egyszerű megoldási lehetőség, hogy a rácspontokat egy gráf csúcsainak fogjuk föl, és akkor kötünk össze éllel két csúcsot, ha szomszédosak, és akadály sem választja el őket egymástól. Ekkor egy szélességi bejárással meghatározhatunk egy legrövidebb utat.
Egy megoldást megkönnyítő észrevétel, hogy a robotnak érdemes minden olyan esetben az x tengely felé lépnie, amikor ezt megteheti. (Ez azért teljesül, mert bármikor léphet oldalra, hiszen nincsenek függőleges akadályok, vagyis nem fordulhat elő olyan, hogy valamilyen lehetőséget elveszít az x tengely felé lépéssel.) Emiatt elég, ha csak olyankor hagyunk döntési lehetőséget a robotunknak, amikor elér egy akadályt. Így akár átfogalmazhatjuk a feladatot robot helyett egy labdára, ami zuhan az x tengely felé, és ha ráesik egy "polcra", akkor eldöntheti, hogy a polc jobb vagy bal végéhez gurul el, mielőtt tovább zuhan.
Ezt figyelembe véve találhatunk egy, a fentebbihez képest lényegesen kisebb gráfreprezentációt a feladathoz: legyenek a gráfcsúcsok az akadályvégpontok, és minden u csúcsból vezessen él azon csúcsokba, amelyek megfelelnek annak az akadálynak a végpontjainak, amelyre ráesünk az u csúcsból. Az éleket súlyozzuk az áthaladás közben megtett távolsággal. Élsúlyozott gráfban legrövidebb út keresésére általános esetben a Bellman-Ford, vagy a Dijkstra algoritmust lehet használni, azonban észrevehetjük, hogy ebben a gráfban nincsen irányított kör, vagyis egy egyszerű dinamikus programozás is megteszi: y koordináta szerinti csökkenő sorrendben határozzuk meg a csúcsokra a hozzájuk vezető legrövidebb út hosszát, a következő rekurzív összefüggésből: D(u)=min{D(v)+W(v,u)|v-ből vezet út u-ba }.
A fentebbi gráfot könnyű O(n2) időben fölépíteni, azonban a legnagyobb tesztesetek megoldásához ez nem elég. O(nlog n) időben fölépíthetjük a gráfot egy "söprő egyenes" algoritmussal (ld. Topcoder tutorial). Képzeljük el, hogy egy függőleges egyenest végigtolunk a pályán mondjuk balról jobbra, és közben számon tartjuk, hogy mely akadályokat metszi. Amikor ez az egyenes elér egy u akadályvégpontot, akkor az egyenesen lévő következő (y koordináta szerint csökkenően) akadály lesz az, amelyikre u-ból esik. Ha az egyenest metsző akadályokat egy STL mapben tartjuk, akkor csak meg kell benne keresni az aktuális akadályt, és eggyel odébb kell léptetni az iterátort, ami O(log n) idejű művelet. Ez a megoldás implementálva: S77SweepLine.cpp
Egy másik lehetőség a gráf felépítésére, hogy lentről fölfelé dolgozzuk fel az akadályokat, és egy lazy propagation segment tree-ben tartjuk számon minden x-re a legmagasabb akadály indexét, vagyis hogy mely x koordinátákon mely akadályokra lehet éppen esni. Szilágyi Dániel megoldása ezt a módszert használja: S77SzilagyiDaniel.cpp
Egyébként pl. ebben az IOI feladatban a söprő egyenes módszert és a szegmens fát is be kell vetni: Pyramid Base
Statisztika:
7 dolgozat érkezett. 10 pontot kapott: Szilágyi Dániel. 9 pontot kapott: Jákli Aida Karolina, Juhász 326 Dániel. 8 pontot kapott: 2 versenyző. 5 pontot kapott: 2 versenyző.
A KöMaL 2013. januári informatika feladatai