![]() |
Az I. 158. feladat (2007. április) |
I. 158. A galaktikus köztársaság központi csillagrendszeréről követek indulnak el, hogy a galaxis összes csillagrendszerébe személyesen elvigyék a köztársaság új lobogóját. A köztársaság vezetői úgy gondolják, hogy a lehető leggyorsabban úgy juttathatják el a lobogókat, ha minden egyes csillagrendszerbe követet küldenek egy hajón. Ekkor a központi csillagrendszertől legtávolabb lévő csillagrendszerbe érkezik meg utoljára a zászló.
Rájöttek azonban, hogy a csillagrendszerekbe megérkező követek tovább is indulhatnának. Sőt, arra is van lehetőség, hogy egy csillagrendszer felé több követ utazzon egy hajón, majd a zászló átadása után mindegyik követ más-más csillagrendszerek felé folytassa útját. Ehhez minden csillagrendszerben elegendő hajó áll rendelkezésre, melyek azonos sebességűek, és tetszőleges számú követet tudnak szállítani.
A köztársaság vezetése úgy döntött, hogy az utóbb leírt módon fogják indítani a követeket. Azt akarják elérni ugyanakkor, hogy a legtávolabbi csillagrendszer felé indított közvetlen hajó megérkezése előtt, vagy azzal egy időben, már az összes további csillagrendszerbe is elérkezzenek a zászlók. Tehát az utolsó lobogó átadásának ideje most sem lehet több, mint a közvetlen hajójáratok indítása esetén.
Számítsuk ki, hogy a közvetlen hajójáratokhoz képest legföljebb mennyivel csökkenthető a hajók összes útja a második követindítási stratégia alapján.
A csillagrendszerek adatait térbeli derékszögű koordinátákkal adjuk meg egy szöveges állományban. Az állomány minden egyes sora egy-egy csillagrendszer X, Y, Z valós koordinátáját tartalmazza egymástól szóközzel elválasztva. Az állomány első sorában a központi csillagrendszer adatai találhatók. A program a parancssorból olvassa be a bemeneti állomány nevét, majd a standard kimenetre írja a közvetlen hajójáratok összes útját, a legrövidebb hajójáratok összes útját, valamint a kettő különbségét.
Beküldendő a program forráskódja (i158.pas, i158. cpp, ) valamint a megoldás rövid dokumentációja (i158.txt, i158.pdf,
).
(10 pont)
A beküldési határidő 2007. május 15-én LEJÁRT.
A feladatra csak két teljes megoldás érkezett, ezeket adjuk mintaként: Danka Miklós András (danka.zip) munkája Pascalban és Györök Péter (gyorok.zip) megoldása Delphiben.
Statisztika:
12 dolgozat érkezett. 10 pontot kapott: Danka Miklós András, Györök Péter. 8 pontot kapott: 3 versenyző. 6 pontot kapott: 1 versenyző. 4 pontot kapott: 1 versenyző. 3 pontot kapott: 1 versenyző. 2 pontot kapott: 3 versenyző. 1 pontot kapott: 1 versenyző.
A KöMaL 2007. áprilisi informatika feladatai