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

KöMaL Problems in Informatics, September 2013

Please read the rules of the competition.


Show/hide problems of signs:


Problems with sign 'I'

Deadline expired on October 10, 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)

solution (in Hungarian), statistics


I. 326. Cities with multiple metro lines provide tourists with maps and route finder services. Budapest currently has 3 metro lines (M1, M2 and M3), with station ``Deák Ferenc tér'' being the only one in their intersection.

You should create a route finder table: upon entering the name of the start location and destination, it should display the corresponding route between these stations. The file allomasok.txt contains station names in the actual order for each of the 3 metro lines.

You should solve this route planning task in a spreadsheet application, but your own functions or any macros should not be used.

Load the UTF-8 encoded and tabulator-separated text file allomasok.txt according to the example, then save the worksheet as i326 in the default file format of the application.

The structure of your table should be similar to the example shown below.

Cells A2 and B2 should contain the name of the start location (``Indulási állomás'') and destination (``Érkezési állomás''), respectively.

The computed route should be displayed in cells B4:B9. Directions should be specified by the name of the last stop of the actual metro line. You can assume that the station name where one can change between the lines, moreover, the last stops of each line are known in advance.

Auxiliary computations can be performed to the right of column G, or below line 22. These computations should be briefly explained in the sheet.

By using a function, cell B4 should determine the starting metro line (``Metróvonal'' is metro line).

By using a formula, cell B5 should determine the starting direction (``Irány'' is direction).

Cell B6 should display the number of stations to be covered until the destination, or until a change between the lines is necessary (``Megállók száma'' is the number of stations).

Cell B7 should contain the name of the new metro line, if a change is necessary (``Átszállás'' is change between the lines). If no change is necessary, cells B7:B9 should remain empty.

Cell B8 should contain the direction after a possible change.

Cell B9 should display the remaining number of stations until the destination.

You should format the table according to the following guidelines and to the example:

a. Cells in the first line should be aligned to the middle, both horizontally and vertically.

b. Column names and other texts in the first line should be displayed in boldface.

c. The content of cells A4:A9 should be aligned to the right.

The spreadsheet (i326.xls, i326.ods, ...) together with a short documentation (i326.txt, i326.pdf, ...) also containing the name and version number of the spreadsheet application should be submitted.

Downloadable file: allomasok.txt

(10 pont)

solution (in Hungarian), statistics


I. 327. Our contestants had to assemble railway tracks based on the instructions of Problem S. 76. proposed last year. That program had to create a string as an output according to the number of track elements: crossings, straight elements and arced elements. For example, if the input is 1 2 8, then the corresponding output is XEJEJJBJXBBB.

Your current task is to graphically display the track in Logo language by using the above (correct or incorrect) output string as input. As a developer environment, we recommend Imagine Logo, downloadable from http://logo.sulinet.hu.

The track image should be created by your function s76. Its input is the character string encoding different track elements. Crossings should be drawn in red, straight elements in blue, while arced elements in green. The size of a straight element should be 40 units. Besides the image itself, your procedure should also display a message whether the track is correct or not. If the track is not closed, or if there are other self-intersections than crossings, a warning should be displayed, but the track should still be drawn according to the string. If there are multiple inconsistencies, displaying one of them is sufficient.

For the solution, you should only use procedures or functions calling one another or themselves. Loops or variables should be avoided. The Imagine Logo project (i327.imp) should be submitted.

(10 pont)

solution (in Hungarian), statistics


Problems with sign 'S'

Deadline expired on October 10, 2013.


S. 82. We would like to place N castles on an N×N chessboard (N\le 1\;000\;000) so that no castle can attack any other castle: two castles attack each other precisely if they are positioned in the same file or rank. To complicate things a bit, some further restrictions are imposed: the ith castle can be placed only in the rectangle spanned by the coordinates (ai,bi) (as upper left) and (ci,di) (as lower right).

Your task is to decide whether this construction can be realized or not. If not, you should display ``NOT''. If yes, you should give a solution: rank and file numbers of each castle should be displayed in a separate line. Castles should be displayed in the same order as the given rectangles: the first line of the output should contain coordinates of the first castle, and so on.

Your program should read the value of N from the first line of the standard input, then the values of the ai, bi, ci, di integers separated by a space from the second line. The output of your program should be given in the first line of the standard output: either a ``NOT'' message, or the castle coordinates should be displayed. In the example, ``Példa bemenet'' is the sample input, while ``Példa kimenet'' is the corresponding output.

Scoring and bounds. You can obtain 1 point for a brief and proper documentation clearly describing your solution. The maximal 9 points for your program can only be obtained if it can solve an arbitrary valid input within 1 second of running time. You can test your program by downloading some sample input-output files from our website. Partial points can be obtained according to the following:

- your program gives a solution for N\le12,

- every rectangle is of size 1×2 or 1×3,

- every rectangle is of size 1×2 or 2×2.

The source code (s82.pas, s82.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (s82.txt, s82.pdf, ...) - also describing which developer environment to use for compiling - should be submitted in a compressed file s82.zip.

(10 pont)

solution (in Hungarian), statistics


$Var(Body)

Upload your solutions above