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. 379. feladat (2015. szeptember)

I. 379. A nyugatot benépesítő telepesek sokan ismerték egymást, akár még leveleztek is volna, de arról gyakran fogalmuk sem volt, hogy egy másik család vajon merre lehet. Postakocsi nem volt, csak a szomszédok találkoztak. Mivel más módjuk nem volt, a terület feltérképezésére a következőt találták ki:

Ha két szomszéd találkozik, akkor kicserélik ismereteiket. Ez azt jelenti, hogy egyik a másiktól megtudja, hogy az kikről tud már. Ha az adott illetőről még nem tudott, akkor feljegyzi a nevét és azt, hogy kitől hallott róla. Ha ezután bármilyen üzenetet kíván egyik telepes egy másiknak eljuttatni, akkor azt kéri meg a továbbításra, akitől először hallott róla.

Megfelelően sok találkozás után mindenki tudomást szerez a terület minden telepeséről.

Feltételezzük, hogy kezdetben mindenki ismeri a szomszédjait, de más családokat nem. A szomszed.txt fájl tartalmazza a szomszédság leírását. A talalkozas.txt pedig a találkozásokat írja le időrendben (ki, kivel).

A standard bemenetről olvassuk be, hogy ki kinek akar üzenetet küldeni. Határozzuk meg, hogy hányadik találkozást követően indíthatja útjára az üzenetet, valamint azt, hogy az üzenet milyen úton jut el a címzetthez.

Példa (a többsoros bemeneteknél a példában a sortörések helyett / jelet írtunk):

A lap nyomtatott változatában a példa hibás volt, ez egy helyes példa.

Beküldendő egy tömörített i379.zip állományban a program forráskódja és megoldás rövid leírását bemutató dokumentáció, amely egyben megadja, hogy a forrás mely fejlesztő környezetben fordítható.

(10 pont)

A beküldési határidő 2015. október 12-én LEJÁRT.


A következő bemeneteket használtuk tesztelésre: i379bemenet.zip

0. a közölt mintabemenet

1. a mintabemenet szomszédai s találkozásai, de a megadott személyek szomszédok

2. a mintabemenet szomszédai s találkozásai, de egy találkozás elég

3. a mintabemenet szomszédai, de sok találkozással

4. egy "lánc" - mindenkinek két szomszédja van, a lánc végén egy-egy

5-7. általános tesztesetek

Minden tesztesetre 1 pont volt szerezhető. Egy további pont azért járt, ha valaki a feladatleírásnak megfelelően kezelte a bemenetet. Az utolsó pont az érdemi dokumentációért járt.


Statisztika:

12 dolgozat érkezett.
10 pontot kapott:Németh 729 Gábor, Tersztenyák Balázs.
9 pontot kapott:Jakab 042 Richárd, Noszály Áron, Rittgasszer Ákos.
8 pontot kapott:1 versenyző.
6 pontot kapott:1 versenyző.
4 pontot kapott:1 versenyző.
2 pontot kapott:2 versenyző.
1 pontot kapott:1 versenyző.
0 pontot kapott:1 versenyző.

A KöMaL 2015. szeptemberi informatika feladatai