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

KöMaL Problems in Informatics, March 2010

Please read the rules of the competition.


Show/hide problems of signs:


Problems with sign 'I'

Deadline expired on April 12, 2010.


I. 235. Your task is to perform some measurements in a complicated, rectangular-shaped maze. The rectangle is divided into a grid of squares. (Two squares are adjacent only if they have a common edge.) There are two types of squares: solid walls and unit squares that are part of a pathway.

The maze has several entrances and some parts of it may be completely inaccessible from outside. Some parts may be accessed by using a particular entrance but not the other. Each side of the rectangle contains at least one unit of wall.

Your program should determine the area of those parts of the maze that can be accessed from outside. You should also give the total wall length and number of entrances of these parts.

The command line argument to your program is the name of the data file describing the maze. The first line of this file contains the number of rows N (3\leN\le1000) and columns M (3\leM\le1000). The following N lines then contain the actual map. Walls are denoted by F, while squares of a pathway are denoted by a space character.

Your program should use the standard output to display the area of the accessible parts of the maze, the length of walls and number of entrances.

In the example, ``Példa bemenet'' is the sample input, ``Kimenet'' is your output, ``a szürke hátterű mezők a bejárható területet mutatják'' is ``grey squares are parts of the pathways'', ``az útvesztő területe 4 egység'' is ``the area of the maze is 4 units'', ``a falak hossza 10 egység'' is ``the length of walls is 10 units'', while ``az ajtók száma 2 darab'' is ``the number of entrances is 2''.

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

(10 pont)

solution (in Hungarian), statistics


I. 236. By downloading files utvonal.txt, kapcsolo.txt and jarat.txt from our web page, you can study the daily flight routes and number of passengers of a certain airlines.

The first lines of these tabulator separated, UTF-8 encoded text files contain the field names.

[1.]

Create a new database ``airlines''. The three files above should be imported into the database with names utvonal, kapcsolo and jarat.

[2.]

When reading these files, appropriate data format and keys should be set. New fields should not be included.

Tables

utvonal (utkod, honnan, hova)

utkod Identifier of the route (number), this is the key;
honnan The flight departs from city (text);
hova The flight lands in city (text);

kapcsolo (utkod, jaratszam)

utkod Identifier of the route (number), key;
jaratszam Identifier of the flight (text), key;

jarat (jaratszam, indul, erkezik, utasmax, foglalt)

jaratszam Identifier of the flight (text), this is the key;
indul The flight departs at (time);
erekezik The flight arrives at (time);
utasmax Maximal passenger capacity of airplanes of this flight (number);
foglalt Number of booked tickets of the flight (number).

Now solve the following task. When a query is answered, no other data, only the requested results should appear. Queries should be named as indicated in the parentheses.

[3.]

Make a query to list in alphabetical order those flights that depart from Budapest. Each city should be listed only once. (3celallomasok)

[4.]

Which is the earliest flight from Vienna to London that has available seats? Give the flight number, the departure time and the number of free seats. (4koran)

[5.]

Determine for each city the number of departing flights with seats available.\ (5varosonkent)

[6.]

Which is the most popular destination city (according to passenger number)?\ (6nepszeru)

[7.]

List those cities which are directly accessible (that is, without transfer) from Vienna but not from Budapest. (7atszallas)

[8.]

We would like to travel the Budapest--Amsterdam--Budapest route in one day. List the departure times of suitable flights from Amsterdam, if we start off from Budapest by the earliest flight, and we spend at most 2 hours in Amsterdam. (8retur)

[9.]

Due to good weather conditions, flights to Dubrovnik land 15 minutes earlier. Make a query that modifies arrival times of all such flights. (9dubrovnik)

The database (i236.odb, i236.mdb, ...) together with a short documentation (i232.txt, i232.pdf, ...) -- also containing the name and version number of the database application -- should be submitted in a compressed file (i236.zip).

(10 pont)

solution (in Hungarian), statistics


I. 237. The Hungarian Academy of Sciences was founded 185 years ago. Wikipedia contains a list together with some other information on the members. This list of 2948 academicians is quite long so it is divided into four parts on the web page.

By copying data from Wikipedia and converting it suitably in some steps, create a data table with names of contemporary members of the Academy. Use only the features and functions of word processors and spreadsheet applications, and avoid manual modifications as much as possible.

For different type of memberships and their starting date, use the most current dates. In the sample (``Minta''), ``Név'' is name, ``Születés'' is year of birth, ``Nemzetiség_és_foglalkozás'' is nationality and occupation, ``Tagság'' is type of membership, and ``Kezdete'' is ``member since''.

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

A valid data table is worth 5 points, while giving steps of the conversion procedure is another 5 points.

(10 pont)

statistics


Problems with sign 'S'

Deadline expired on April 12, 2010.


S. 52. In the figure you see a lake in which a snake is hiding. The snake winds only horizontally and vertically. (There are no parts of the snake for which the corresponding squares have a common vertex only.) Black squares are rocks and the snake can not pass them. Numbers below the figure denote how many squares in the actual column contain squares that are part of the snake. The head and the tip of the tail of the snake are above the water level, so we can spot those.

Your program should give the complete position of the snake in the lake. The first command line argument to your program is the name of the file containing known data for the lake and the snake. The first line of this file describes the side length N (3\leN\le20) of the square-shaped lake and the length of the snake M (3\leM), while the four numbers E1, E2, V1 and V2 (1\leE1,E2,V1,V2\leN) in the second line give the coordinates of the head and the tail of the snake.

The number of rocks in the lake K (0\leK\leN) is given in the third line. The following K lines then contain two integers: coordinates of each rock. The last line contains N numbers: the number of snake-parts in each column.

The second command line argument to your program is the name of the output file. It should contain N lines depicting the lake and the position of the snake. Each square of the lake should occupy 3 characters. Water in the lake is denoted by spaces (this is seen as grey squares in the example). Body of the snake is denoted by integers: corresponding distances from its head. If this puzzle has no solution, then the content of the output file should be ``No solution''.

In the example, ``Példa bemenet'' is the sample input, while ``Kimenet'' is the output.

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

The idea of this exercise is taken from the web page of Hungarian logic puzzles.

(10 pont)

solution (in Hungarian), statistics


$Var(Body)

Upload your solutions above