KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem I. 379. (September 2015)

I. 379. Many settlers in the West knew each other, but they often had no idea about the whereabouts of some other families. A postal service did not yet exist, and only the neighbors met each other. Having no other alternative, they wanted to map their region as follows.

When two neighbors meet, they exchange information. That is, they both let the other know about the people he or she knows about. If this neighbor did not know about someone earlier, then he or she records the new name together with the name of the person sharing this piece of information. Then, if a settler wants to pass on any information to another settler, the sender asks the person to transmit the message who first informed the sender about the recipient's whereabouts.

After sufficiently many encounters, everybody will know about every other settler in the region.

We assume that initially everybody knows their neighbors, but no other families. The file szomszed.txt describes the neighborhood relations, while the file talalkozas.txt contains the encounters in chronological order (who met whom).

Your program should use the standard input to read who wants to send information to whom. Then the program should determine the number of encounters after which the message can be sent, and the route the message travels from the sender to the recipient.

In the example, line breaks in multiple-line inputs have been replaced by the slash character (/); ``Bemenet'' means input, while ``Kimenet'' is the corresponding output.

The source code of your program, together with a short documentation describing your solution and specifying the developer environment to use for compiling the source, should be submitted in a compressed file i379.zip.

(10 pont)

Deadline expired on 12 October 2015.


Statistics:

12 students sent a solution.
10 points:Németh 729 Gábor, Tersztenyák Balázs.
9 points:Jakab 042 Richárd, Noszály Áron, Rittgasszer Ákos.
8 points:1 student.
6 points:1 student.
4 points:1 student.
2 points:2 students.
1 point:1 student.
0 point:1 student.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley