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

KöMaL Problems in Informatics, February 2010

Please read the rules of the competition.


Show/hide problems of signs:


Problems with sign 'I'

Deadline expired on March 10, 2010.


I. 232. In this exercise a simple model of communication over the Internet by using packets is described.

Typical communication software breaks messages of communicating parties into pieces of standard size and appends some auxiliary data necessary for the transmission. These packets are then sent through the appropriate channels. Packets may arrive to the recipient in a different order they were sent.

The structure of each packet containing pieces of messages is as follows.

sender identifier of the sender, positive integer, at most 100;
addressee identifier of the recipient, positive integer, at most 100;
message identifier a unique number, at most 1\ 000\ 000
number of the fragment gives the number of the fragment of the actual message, the number of the first fragment is 1, and numbering is sequential;
part of the message consists of exactly 10 characters. The last significant character of the message is followed by at least one filter character (|) so that the total length of the piece is always 10 characters. (Messages consist of lower and uppercase characters of the English alphabet, digits, punctuation marks, hyphens and spaces.) Instead of the space characters however, an underscore is used for simplicity;
checksum is the remainder upon dividing the sum of the above 4 numbers and ASCII codes of message characters of the packet by 100.

We test this network model by writing all incoming pieces of messages into the file naplo.txt, shown in the example.

The first line of the example shows that Station 11 has sent a message to Station 3. The message identifier is 334. The actual packet contains the second fragment of this message. Since we see a filter character (|), we know that this is the last piece of the message.

Write your program halo to answer the following questions. Your program should process each correct input file. Display the number of each task as well. If your program needs user input, print the corresponding query in detail (in the fifth task, for example: ''5th task: Enter the message text''). You may omit diacritical marks when displaying messages on the screen.

[1.]

Read the file naplo.txt (naplo.txt) and use that information to solve the following questions. If, for some reasons the file can not be read, enter data for 10 messages manually and use that in the following.

[2.]

Display on the screen the number of messages Station 4 sent to Station 5.

[3.]

Display on the screen numbers of those lines with invalid checksum, separated by a space. Otherwise display ``All checksums were correct.''

[4.]

By processing the file naplo.txt, recover the original messages. Each line of the file eredeti.txt should contain one message and its structure should be similar to our second example. (The second example shows a possible beginning of eredeti.txt that would correspond to our first input example.) Messages can be given in an arbitrary order.

eredeti.txt

11 3 334 KoMaL_pontverseny ...

[5.]

Decompose a message of the user into packets. The user should also specify the source and destination Stations. Each packet should be displayed on the screen in separate lines. Be careful to produce a unique (but otherwise arbitrary) message identifier to avoid naming collisions.

The source code (i232.pas, i232.cpp, ...) together with a short documentation (i232.txt, i232.pdf, ...) -- also describing which developer environment to use for compiling, further a brief description of your solution -- should be submitted in a compressed file (i232.zip).

(10 pont)

solution (in Hungarian), statistics


I. 233. In this exercise we do treasure hunting by using a spreadsheet application.

The game takes place on a 10×10 board. 5 cells contain treasure. You control a robot on the board and your aim is to collect as many pieces of treasure as possible. The robot grabs the treasure if it occupies a treasure cell. You, the player, see all the treasures in advance. Your task is to give a single command line to the robot so that it can collect as many treasures as possible.

Coordinates of the starting position of the robot are given in two cells. The robot, in its default position, faces downwards. The string written in cell A1 controls the movement and direction of the robot. The table below explains the control characters.

e 1 step forward in the actual direction
j Turn right by 90 degrees (compared to the actual direction)
b Turn left by 90 degrees (compared to the actual direction)

You should write functions into the cells whose results upon evaluation are useful for conditional formatting, for setting patterns and background colors and displaying events.

Coordinates of the treasure cells are given in 5×2 cells of the sheet. Treasure cells should be denoted by red cells, while path of the robot according to the command line in cell A1 is black. Treasure cells should not change color when the robot finds them.

You should display the number of treasures the robot acquired by using the actual command line.

Copyable formulae should compute the position and direction of the robot. During the play it is not necessary to check whether the robot leaves the board or not. You should not use macros or program modules. All (auxiliary) computations should be clearly visible, do not hide anything.

Your spreadsheet (i233.xls, i233.ods, ...) together with a short documentation (i233.txt, i233.pdf, ...) -- also describing the name and version number of the spreadsheet application, further a brief description of your solution -- should be submitted in a compressed file (i233.zip).

(10 pont)

statistics


I. 234. With the help of the tool on http://prezi.com you should create a presentation introducing your school. Your presentation should contain at least one video besides texts and images. Content and uniformity are the two main aspects of our evaluation. You should not change your presentation after the deadline is over.

You should submit a file i234.pdf containing the web address of your presentation, further, the sources of materials you have used.

(10 pont)

solution (in Hungarian), statistics


Problems with sign 'S'

Deadline expired on March 10, 2010.


S. 51. Ultra-thin clients were introduced at a certain company when its computer network infrastructure was updated. This means that desktop computers were replaced by simple devices only capable of forwarding keyboard and mouse input to a central server, and displaying the server's output on the local screen. All computations and programs are effectively run on the central server.

However, one disadvantage of this system is its sensitivity to network delays, so the server must be placed optimally such that the maximal delay from a client to the server is minimal.

Your program should determine the network delay between the server and the farthest client if the server is optimally positioned. The network topology is a tree, that is, every two nodes are connected by exactly one path. Clients are located at final nodes of the network, that is, they are the leaves of the tree. The server should be put at some inner node.

Description of the network is read by your program from the standard input. The first line of the input contains a single integer, the number of nodes 1\le N\le 10\;000. Then each of the following N-1 lines contains 3 integers separated by space: the Xi and Yi endpoints of the ith network connection (1\leXi,Yi\leN) together with its delay 0\leDi\le1000. (The time needed to process data at the two endpoints can be neglected.)

Your solution is written on the standard output. It should contain only a single line with an integer: the maximal delay in an optimal location of the server.

In the example, ,,Példa bemenet'' is sample input, ,,Példa kimenet'' is sample output, ,,Hálózati topológia'' is network topology, while ,,A szerver a bekeretezett (8-as számú) csomópontba kerül'' means that the server should be positioned at node 8 (framed).

Sample test cases: s51test.zip

(10 pont)

statistics


$Var(Body)

Upload your solutions above