Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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, \ldots) valamint a megoldás rövid dokumentációja (i158.txt, i158.pdf, \ldots).

(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