Az S. 53. feladat (2010. április)

S. 53. Bergengóciában, a már megismert Villamoshajtó Bajnokság mellett, nagy hagyományokkal bíró nemzeti sportesemény a Mezei Kincsfelderítő és -begyűjtő Torna. Noha az idei szabálymódosítás értelmében -- miszerint a kincsek felkutatásához kémműholdak is igénybe vehetők -- a felderítéshez bevetett taktikák alapvetően megváltoztak, a kincsek gyors összegyűjtése továbbra is kihívást jelentő feladat maradt.

Írjunk programot, mely az egyes kincsek elhelyezkedése és értéke, illetve a rendelkezésre álló időkeret alapján meghatározza, hogy milyen útvonalon haladjunk, azaz milyen kincseket és milyen sorrendben érintsünk, hogy a lehető legnagyobb összértékű kincshalmazt gyűjthessük össze. Feltehetjük, hogy egy kincs begyűjtéséhez szükséges idő elhanyagolható; hogy utunkat bármelyik kincstől indíthatjuk; illetve hogy egy időegység alatt egy távolságegységet tudunk megtenni.

A program a mező leírását a standard bemenetről olvassa. Ennek első sora két, szóközzel elválasztott egész számot tartalmaz: a kincsek 1N1000 számát, illetve a rendelkezésre álló időkeretet. Az ezt követő N sor mindegyike három, szóközzel elválasztott egész számot, az i-edik kincs koordinátáit és 0C_i1000 értékét tartalmazza.

A program a megoldást a standard kimenetre írja. Ennek első sorában az összegyűjtött kincsek 1KN száma szerepeljen, további K db sorában pedig az összegyűjtött kincsek sorszámai a begyűjtés sorrendjében (1-től indexelve).

A feladatra nem (csak) optimális megoldásokat várunk. A beérkezett megoldásokat rangsoroljuk a különféle teszteseteken elért futási eredmények alapján. (A megoldásokat egy Core 2 architektúrájú, 2 GHz-en működő processzoron futtatjuk. Egy program egy teszteseten legfeljebb 10 percig dolgozhat, az ennél tovább futó programoknál az adott tesztesetet nem értékeljük.) Az első helyezett 10, a második 9, a többi megoldás pedig legfeljebb 8 pontot kaphat.

Beküldendő egy tömörített s53.zip állományban a program forráskódja (s53.pas, s53.cpp, ...), valamint a program rövid dokumentációja (s53.txt, s53.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.

(10 pont)

A beküldési határidő 2010. május 10-én LEJÁRT.

Statisztika:

6 dolgozat érkezett.
10 pontot kapott:	Adrián Patrik, Borsos 607 Zalán, Éles András, Nagy 111 Miklós.
8 pontot kapott:	1 versenyző.
5 pontot kapott:	1 versenyző.

A KöMaL 2010. áprilisi informatika feladatai