KöMaL - Középiskolai Matematikai és Fizikai Lapok
A lap

Rendelje meg a KöMaL-t!



VersenyVizsga portál


Matematika oktatási portál

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 points)

Deadline expired on 12 October 2015.

Statistics on problem I. 379.
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.

  • Problems in Information Technology of KöMaL, September 2015

  • Támogatóink:   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