Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem I. 325. (September 2013)

I. 325. Mailing lists can provide efficient communication between people having a common interest. There are several rules governing these lists; in the present task we will focus on the following one: if one wishes to share some thoughts concerning a particular email, then one has to reply to that email, and should not post it with a new topic. Many mailing list programs can keep messages with the same topic separated, hence information can be retrieved more easily.

In the present exercise you will solve several tasks concerning the log file (``napló'' in Hungarian) of such a mailing list. Each line of the file naplo.txt corresponds to one message. Each line contains two integers, one positive integer and a non-negative integer, separated by exactly one space character: the first number is the sender's identifier, the second number is the identifier of the message the sender replies to. If a new thread is started, then the second number is 0. The first integer is at most 100, and the log file has at most 2000 lines.

The first few lines of the naplo.txt file is shown below.

Your program (i325.pas, i325.cpp, ...) should solve the following tasks. First, the number of the actual task (e.g., ``Task #6'') should be displayed together with a message briefly describing the type of the input (e.g., ``Enter the identifier of the email:''). Diacritical marks in the output may be omitted.

1. Read and store data from the file naplo.txt in an appropriate format for later processing.

2. Display the number of messages the log file keeps track of.

3. Display the identifier of the first message in every thread, separated by a space character.

4. Give the number of messages that nobody replied to, and with no preceding message in the actual thread.

5. Determine the 5 most active senders. Display the sender's identifier first, then the number of messages they sent, separated by a tabulator character. Senders should be sorted according to decreasing number of messages. Each line should correspond to one person. Displaying 5 lines is sufficient even if more people sent the same number of messages.

6. Prompt the user for a message identifier. You should then display the chain of messages from the first message in its thread to the given one in one line. The message identifier of the given mail should be displayed first, and the thread's opening message last. Identifiers should be separated by a space character.

7. There are messages generating a lot of off-topic discussion, that is, content not related to the original question. Prompt the user for the message identifier of such an off-topic email, then display the sender identifiers replying to that mail. Each sender should be displayed only once.

8. Prepare the file rend.txt containing message identifiers in the following ordered form. The first item in each line is the number of the thread's opening message, then you should create separate groups in parentheses: messages in each group are direct replies to the thread's opening message. Within the group, you should create further groups in parentheses recursively, containing the message identifiers directly replying to the first message in the actual group.

The sample output corresponding to the given input is displayed below.

The source code (i325.pas, i325.cpp, ...) together with a short documentation (i325.txt, i325.pdf, ...), also describing which developer environment to use for compiling, should be submitted in a compressed file i325.zip.

Downloadable file: naplo.txt

(10 pont)

Deadline expired on October 10, 2013.


Sorry, the solution is available only in Hungarian. Google translation

A 16 megoldó 7 különböző programozási nyelven oldotta meg a feladatot. 4-4 C++ és FreePascal, 3 C#, 2 Java, 1-1 C, Python, Visual Basic megoldás érkezett.

Az utolsó feladat túlmutatott az érettségin kitűzhető feladatok szintjén, de a versenyzők fele tökéletesen megoldotta, míg 5 fő nem is próbálkozott vele. Ezen részfeladat megoldásához egy rekurzív függvényt praktikus készíteni: ez zárójelezve jeleníti meg az összes közvetlen reagálás sorszámát, közben minden megtalált levélre meghívja önmagát. A zárójelezésre praktikus figyelni.

Típushibának számított, hogy a megoldók nem kezelték azt a helyzetet, amikor a levélírók száma nem éri el az ötöt.

Az értékelési útmutató: levlistaertekeles.pdf

A megoldások közül Kovács Balázs Marcell munkáját közöljük: i325.cpp és egy versenyen kívül érkezett megoldást annak rövidsége miatt: levlista.cxx


Statistics:

16 students sent a solution.
10 points:Fényes Balázs, Kovács Balázs Marcell.
9 points:Csernák Tamás, Fehér Balázs, Kiss 107 Ádám, Németh 123 Balázs, Uzonyi 000 Ákos.
8 points:1 student.
7 points:3 students.
6 points:3 students.
4 points:2 students.

Problems in Information Technology of KöMaL, September 2013