3. Domácí úkol - agneti

Čtěte prosím tuto stránku celou a pozorně.

Zadání

Během noční hry Matrix 2006 bylo nutné splnit následující úkol: Ve Stromovce bylo rozmístěno 13 agentů, každý měl své jméno. Týmy měly na začátku 5 vizitek se jmény. Kdo dal vizitku agentovi s odpovídajícím jménem, mohl si vybrat jinou vizitku podle barvy. Ta odkazovala zase na dalšího agenta. Cílem bylo získat vizitky 3 barev s jménem hlavního (spřáteleného) agenta.

Pro úplnost je potřeba znát ještě několik detailů:

• Tým má pět členů,
• tým má od začátku k dispozici mapu s rozmístěním agentů,
• tým předem neví, jaké vizitky má u sebe dotyčný agent,
• žádná z pěti počátečních vizitek nevede na spřáteleného agenta.

Napište program, který prozkoumá síť agentů a najde optimální postup, který by měl být použit v případě, že tým od začátku znal síť agentů. Kritérium pro optimální postup je čas, který je potřeba k doručení všech tří vizitek hlavnímu agentovi. Čas je dán délkou nejdelší trasy. Vzdálenost agentů je možné odhadnout pomocí vzdušné vzdálenosti (lze ji odečíst z mapy).

Hint

Použijte Dijkstrův algoritmus pro hledání nejkratší cesty v grafu. Jeho podrobný popis najdete například v učebnicích:

• Pavel Töpfer: Algoritmy a programovací techniky
• Matoušek, Nešetřil: Algoritmy a programovací techniky

Odkazy na webu:

• Dijkstra's Algorithm
• Dijkstra's Algorithm operation

Formát vstupu a výstupu

Vstup je zajištěný pomocí unity Stromovk.pas. Použití unity by mělo být jasné z komentářů ve zdrojovém kódu.

Výstupem je soubor vystup.txt, který obsahuje tři řádky se třemi trasami, které vedou k doručení tří různě barevných vizitek hlavnímu agentovi. Na každém řádku je nejprve číslo agenta (ID), které musí odpovídat jedné z pěti vizitek, které měl tým na počátku. Dál následuje seznam barev vizitek, které má hráč postupně chtít po jednotlivých agentech. Barvy jsou kódovány pomocí písmen R, G, Y. Číslo agenta i barvy jsou oddělené mezerou. Na konci řádku může být jedna mezera navíc.

Příklad:

5 R G Y R R G Y
3 R R R G Y G
4 R G G G G R

Ze zadání je jasné, že každý ze tří řádků by měl končit na jiné písmeno. Na pořadí řádků nezáleží.

Ukázková data

Příklady souborů s výstupem a soubor stromovk.pas najdete v archivu data.tar.

FAQ

Mohou dvě nebo více z pěti vizitek, které tým na počátku dostane, odkazovat na stejného agenta?

Ano, mohou. Teoreticky může všech pět vizitek směřovat na stejného agenta.

Budou se ve všech vstupech vyskytovat vždy jen tři barvy a budou to vždy barvy R G Y ?

Ano.

Kolik vizitek má agent?

Teoreticky neomezené množství vizitek pro každou barvu. Každý agent měl tři dostatečně tlusté balíčky vizitek - pro každou barvu jeden balíček.

Co je to "vizitka s odpovídajícím jménem"?

Je to vizitka s jménem agenta, kterému je právě předávána.

Můžu si řešení rozdělit do více souborů, nebo musím vše vtěsnat do agenti.pas?

Samozřejmě je to možné. Rozdělení do více souborů je téměř vždy dobrá věc.

Může se stát, že nějaký vstup nemá žádné řešení?

Všechny ukázkové i testovací vstupy budou mít řešení. Může se ale stát, že pro některý lístek nebude existovat cesta k hlavnímu agentovi.

Poznámky

• Formát vstupu a výstupu je povinný, jeho nedodržení je považováno za chybu.
• Program by kromě vstupního textového souboru neměl požadovat žádná data (ani z klávesnice).
• Do programu prosím vložte komentář se svým jménem a příjmením.
• Řešení posílejte mailem na adresu hruska (zavináč) popelka (tečka) ms (tečka) mff (tečka) cuni (tečka) cz s předmětem zprávy PGM - agenti a s přiloženým souborem agenti.pas.
• Po odeslání mailu s domácím úkolem by vám měla přijít zpět zpráva s potvrzením příjmu.
• Neposílejte .exe soubory.
• V případě jakýchkoliv nejasností nebo problémů mi pošlete mail.

Termíny

Termín zadání: 15.12.2006.
Termín odevzdání: do 7.1.2007 včetně.
Termín odevzdání oprav: do 31.3.2007 včetně.