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, April 2012

Please read the rules of the competition.

Problems with sign 'I'

Deadline expired on 10 May 2012.

I. 292. In this exercise you are going to simulate the path of a robot moving on a huge grid. In each step the robot advances one unit parallel to one of the coordinate axes. The robot starts from point (0,0) and executes a predefined series of steps consisting of letters E, H, J and B. Suppose that the current position of the robot is (x,y), then command E (forward) will move the robot to (x,y+1), command H (back) to (x,y-1), command J (right) to (x+1,y), and command B (left) to point (x-1,y).

The grid contains some checkpoints. After each step the robot records the sum of distances from the checkpoints. The distance of two points is now the Manhattan distance, for points (x1,y1) and (x2,y2) it is defined as |x1-x2|+|y1-y2|.

The first command line argument to your program is the name of an input file containing the necessary data. The first line of this file contains the number of checkpoints N (1\le N\le 100\;000) and the number of steps M (1\le M\le
300\;000). The following N lines then contain the x and y coordinates of the checkpoints (-1\;000\;000\le x,y\le +1\;000\;000) separated by a space. There can be some checkpoints having both coordinates equal. The next line finally contains M characters (EH, J or B) describing the steps of the robot.

The second command line argument to your program is the name of the output file. It should have M lines, each containing an integer, being the above sum of distances after each step.

In the example, Bemenet is the input and Kimenet is the corresponding output.

Your program should solve the task within 1 second. Due to the high number of grid points and checkpoints, it may be useful to make appropriate preparations before computing the sum of distances to improve the efficiency of your program.

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

Based on a problem of Adrian Satja Kurdija, Croatian Open Competition in Informatics

(10 points)

Solution (in Hungarian)

I. 293. Radio channels are broadcast from several stations throughout the country. In Hungary, May 2010, this was the topic of the database management task of the informatics matriculation exam in English. However, that exam was based on the data collected in 2009. Radio channels and broadcasting data changed since then. In this exercise, you are going to investigate these changes. The files aregi.txt, auj.txt and telepules.txt contain the broadcasting data for 2009 and 2012, further, the location data, respectively.

[1.] Create a new database with name i293. Import the data tables into the database with names aregi, auj and telepules. These txt data files are tabulator separated files in UTF-8 encoding, with field names in the first lines. You should add a unique identifier azon to the tables aregi and auj.

[2.] After importing, you should set the appropriate data formats and keys.


aregi (azon, frekvencia, teljesitmeny, csatorna, adohely, cim) containing data from 2009

azon   identifier of the actual element of the frequency list (counter), this is the key;

frekvencia   the broadcasting frequency in MHz (number);

teljesitmeny maximal broadcasting power in kW (number);

csatorna   name of the radio channel (text), or empty if there is currently no broadcast;

adohely   name of the settlement containing the station (text);

cim   location of the station within the settlement (text), or empty if this is the only station there auj (having the same field names and types as table aregi) containing data from 2012;

telepules (nev, megye)

nev   name of the settlement (text), this is the key (and has all the settlement names in the task);

megye  name of the settlement's county (text).

Radio stations are grouped into 3 categories according to the table. Kategória is category, Sugárzási teljesítmény is broadcasting power, helyi is local, térségi is regional, országos is national. ``0,1 kW és alatta'' is ``0.1 kW or below'', ``0,1 és 1 kW között'' is ``between 0.1 and 1 kW'', while ``1 kW és fölötte'' is ``1 kW or above''.

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

[3.] By using a query, list those settlements from which the channel ``MR1-Kossuth Rádió'' is broadcast in 2012. Each settlement should appear only once and in alphabetical order in the list. (3kossuth)

[4.] List those settlements from which only one channel was broadcast in 2009. (4egy)

[5.] Create a query to list those channels in 2009 that are no longer broadcast this year. (5megszunt)

[6.] By using a query, list those stations, locations and frequencies where the name of the channel changed. Your list should contain the frequency, the old and the new channel names, the settlement name and the location. (6valtas)

[7.] By using a query, list those settlements where a station was created since 2009. (7ujak)

The following exercises should be based on the current (year 2012) data.

[8.] Create a query to determine for each county the number of settlements having a station. (8megyenkent)

[9.] By using a query, give the name of the regional channel (see the table about broadcasting powers) which is broadcast from the most stations. (9nepszeru)

[10.] By using a query, list the names of those settlements that simultaneously broadcast local, regional and national channels. Each settlement should appear only once in the list. (10vegyes)

[11.] Create a query to determine for each settlement (település in the table) the number of local, regional and national channels. Channels with unknown broadcasting power or channel name should be ignored. (11sugarstat)

Your database (i293.odb, i293.mdb, ...) together with a short documentation (i293.txt, i293.pdf, ...) - also describing the name and version number of the database application - should be submitted.

(10 points)

Solution (in Hungarian)

I. 294. Lissajous curves are obtained if we trace the path of a point mass influenced by two perpendicular oscillations. These curves can have intricate shapes depending on the choice of the parameters. To describe these curves in Cartesian coordinates, we let x(t)=A_1 \sin\, (\omega_1 t+\varphi_1) and y(t)=A_2 \sin\, (\omega_2
t+\varphi_2), where x(t) and y(t) are the two coordinates of the point as functions of time, A1 and A2 are the amplitudes, \omega1 and \omega2 are the angular frequencies, finally, \varphi1 and \varphi2 are the phase angles corresponding to time t=0.

You should create a Logo procedure to display the orbit of the point. For simplicity, we fix A1=A2=400 pixels and \varphi1=0.

The name and parameters of your procedure should be lissa o1 o2 fi2, where o1, o2 and fi2 are the values of \omega1, \omega2 and \varphi2.

The Logo project file (i294.imp, i294.lgp) containing the procedure, together with a short documentation (i294.txt, i294.pdf, ...) and the name of the program you have used should be submitted.

(10 points)

Solution (in Hungarian)

Problems with sign 'S'

Deadline expired on 10 May 2012.

S. 71. Our spaceship was suddenly intercepted by some extraterrestrial beings demanding we present a proof about our intelligence, otherwise they destroy our ship. (The fact alone that we have constructed our spaceship is not a satisfactory proof for them.)

We of course do have 8 data files prepared for such emergency situations to yield proof of our intelligence. The extraterrestrial beings unfortunately also require that the proof be at most 64 KiB large. Hence we cannot send them the data files directly, only a program to reproduce the data files when run. More precisely, we can only send the C++ or Pascal source code of this program (because those beings clearly are in possession of such compilers).

Your task is to create a program that accurately reproduces as many of the 8 data files (downloadable from our website) as possible, in such a way that the total size of the source code of your program (possibly together with any auxiliary files it uses) does not exceed the prescribed limit.

Contrary to the usual custom, you do not have to put comments in the source code, and instead of using the standard output, the content of the data files should be written in files (using their original names). However, you still have to submit a separate documentation containing your observations to do the reconstruction, the description of your algorithms and the name of the developer environment to compile your source code. Your solution should contain only the source code and no other executable (machine-code) elements.

Submitted solution will be ranked according to the number of data files reproduced perfectly: the winner gets 10 points, the next contestant 9 points, then 8 points, and the others 7 points at most. (In case of a draw, we rank them according to the size of the source code.)

The source code (s71.pas, s71.cpp, ...) without the .exe or any other auxiliary files generated by the compiler should be submitted in a compressed folder s71.zip, also containing a short documentation (s71.txt, s71.pdf, ...) with a brief description of your solution and the name of the developer environment to use for compiling.

The data files to be compressed can be downloaded here: s71.zip.

(10 points)


Send your solutions by e-mail to:


Támogatóink:   Ericsson   Google   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