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

Problems in Information Technology, September 2010

Please read the rules of the competition.

Problems with sign 'I'

Deadline expired on 11 October 2010.

I. 244. We compress geometric figures consisting only of few colours. For each row, only the difference between the actual row and its predecessor is stored in the compressed file. There is no entry for a row in the compressed file, if that row is identical to the previous one.

You can download the file zaszloX.be from our web page (zaszlo5.be). The first line of the file contains the number of rows N (1\leN\le100) and columns M (1\leM\le100) of the image. The following lines describe the compressed image, in an increasing order in each line and in each column. The first number refers to the corresponding row of the uncompressed image, while the second and third numbers are the starting and ending positions between which the uppercase letter in the fourth position is repeated.

In the example, zaszlo5.be is the encoded image, and ``Az eredeti kép (a dán zászló)'' is the original image, being the Danish flag.

Your program i244 should solve the following tasks by using the data in the file zaszloX.be given as the first command line argument to your program. The number of the actual task (e.g. ``Task #3'') should always be displayed.

[1.] Read the content of the input file and store it in an appropriate data structure.

[2.] Create and display the uncompressed image. A space character should appear between the letters.

[3.] Display the number of different colours (letters) appearing on the image.

[4.] You should save the image as zaszloX.ki (specified by the second command line argument), but by using a different compression method. The original image of N rows should be compressed into N rows: each row of the compressed image should contain uppercase letters describing a colour and the number of repetitions of that colour, each separated by a space. The second example shows again the Danish flag compressed by this method.

[5.] Your program should ask for a character position of the image, then display its colour and the size of the largest connected block of letters of the same colour that character is part of.

[6.] Display the original image in double size: each letter of the original image should correspond to a 2×2 block of identical letters of the magnified image.

The source code and project files of your solution -- without the .exe or any other auxiliary files generated by the compiler -- should be submitted together with a short documentation (i244.txt, i244.pdf, ...) in a compressed folder i244.zip. (Idea is taken from an OKTV 2009 Informatics Competition problem.)

(10 points)

Solution (in Hungarian)

I. 245. Six families have just moved into a new house with 6 flats in Twitter Street. Each of them likes to have a little chat with the other families. The guest tells everything of him- or herself to the inviter, all information he or she knows about the others, including their previous address. Of course, the inviter also shares all known information.

Determine at least how many meetings are needed so that each family knows of every other's original address.

Your solution should be prepared by using a spreadsheet application. Each line records a meeting (beginning with line 4). Column A contains the number of the inviter family, while column B the guest. Families are numbered from 1 to 6.

The result should appear in cell A1. (In the example ``23 találkozás szükséges'' is ``23 meetings are necessary''.) Cell A1 should remain empty, if the given appointments are insufficient to realize the desired final state.

You may use auxiliary cells, program modules and macros however can not be used. You can assume that altogether at most 300 meetings will take place.

Your spreadsheet (i245.xls, i245.ods, ...) together with a short documentation (i245.txt, i245.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 (i245.zip).

(10 points)


I. 246. One can play the following game on a table of N×N cells. Initially all cells are blue. If you click on a cell, that cell and its side neighbours will change colour: blue cells will turn into red and red cells will turn into blue. The aim is to reach a given state of the board.

You should create this game so that it can be played on a web page. The page should contain 2 tables: the first table should be initially blue and the player can modify this table. The second table should show the final state: it should be random but a solution must exist. The player clicking on the first table tries to reach the state of the second table. If the player is successful, your program should display the number of steps required, further the fact if the solution could have been achieved by using fewer steps. You may use html and javascript elements.

The file i246.html should be submitted together with any GIF, JPEG or PNG images that might be required, further, a short documentation (i246.txt or i246.pdf) of your solution, all compressed in a file i246.zip.

(10 points)


Problems with sign 'S'

Deadline expired on 11 October 2010.

S. 55. It is well known that one knight can visit each square of the chessboard such that each square is touched exactly once. (There is an easy algorithm for this.) Your task is now a little harder: the first few steps are already done.

Your program should find the longest possible completion of this path. The first command line argument of your program is the name of the file containing the steps already taken. The second command line argument is the name of the file where the rest of the path should be written. Both files have the same structure: the first line contains the number of steps (\(\displaystyle L\)) already taken, and the second line contains names of the \(\displaystyle L\) fields with the actual steps, separated by spaces.

The example shows a possible beginning.

A1 B3 C1 A2 B4 C2


[] The size of the chessboard is 6x6, fields are denoted as usual.

[] The of the input file is the same as the first square of the output file.

[] If the path can not be continued, a character ``1'' should be written in first line, and the second line should contain the actual position of the knight.

The source code and project files of your solution -- without the .exe or any other auxiliary files generated by the compiler -- should be submitted together with a short documentation (s55.txt, s55.pdf, ...) in a compressed folder s55.zip.

(10 points)

Solution (in Hungarian)

Send your solutions by e-mail to:


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