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

# KöMaL Problems in Informatics, January 2012

Show/hide problems of signs:

## Problems with sign 'I'

Deadline expired on February 10, 2012.

I. 283. In problem I. 277 proposed 2 months earlier you had to display the location and the number of inhabitants of settlements by using geographical coordinates. You are again given the same file helyforr.dat (downloadable from our webpage) containing the name (without diacritical marks), geographical coordinates and number of inhabitants of Hungarian settlements.

Create your program i283 to display the settlements and their names on the screen in a rectangle. Coordinates of this area to be displayed are specified by the user. Points representing settlements should fill up the rectangle. Names of the settlements should not overlap in the rectangle: in this case, certain names should not be displayed. Names corresponding to settlements with greater population should be displayed first. The top left corner of a box containing a name should be positioned according to the geographical coordinates of the settlement. Names can cover up points representing settlements, but not other names. A name -- at the given resolution -- should not be displayed if it overlapped another name (in the prescribed display order), or if it crossed the rectangle boundary.

Your program reads the geographical coordinates, the number of inhabitants and the name of the settlement from the above file. The first line of the file contains the number of settlements $\displaystyle n$ together with the horizontal ($\displaystyle dx$) and vertical ($\displaystyle dy$) size of the rectangular map on the screen ($\displaystyle 256\le dx,dy\le 1024)$. Then each of the following $\displaystyle n$ lines contains data for the settlements. The first two pieces of data of the actual line are the longitudinal and latitudinal coordinates in minutes. The third quantity is the population, while the last piece of data is the name (without any diacritical marks).

In the first table, A helyforr.dat állomány tartalma'' is the content of the file helyforr.dat.

In the example, Bemenet a billentyűzetről'' is the input from the keyboard, A térkép bal felső és jobb alsó sarkának földrajzi koordinátái (egész számok)'' shows the (integer) coordinates of the top left and bottom right coordinates of the actual map, while Kimenet'' is the output.

The source code (i283.pas, i283.cpp, ...) together with a short documentation of your program and solution (i283.txt, i283.pdf, ...) --  also specifying the name of the developer environment to use for compiling the source file -- should be submitted in a compressed file i283.zip.

(10 pont)

solution (in Hungarian), statistics

I. 284. Vitamins are essential, biologically active organic compounds. Data for some vitamins are available in the file vtabla.txt. The other file vitforras.txt specifies which food contains which vitamin.

1. Create a new database named vitamin. Data tables should be imported into the database using the names vtabla and vitforras. The txt files are tabulator separated text files in UTF-8 encoding with field names in the first line.

2. Upon creating the database, you should set the appropriate data types and keys. Add a unique identifier azon to the table vitforras.

Table:

Now solve the following tasks and save them by using the names in parentheses. No other fields, only the requested results should appear.

3. List by a query names of water-soluble vitamins together with their minimal and maximal daily intake. (3vizben)

4. Make a query to list all foods containing vitamin B12. (4b12)

5. By using a query, give the name of those foods that contain at least two vitamins. You should display the name of the food together with the number of vitamins in it. (5tobb)

6. By using a query, list the name of those foods that contain vitamin A together with some other vitamin(s). Each vitamin name should be listed only once, but vitamin A should not be displayed again. (6avit)

7. Using a query, list the name of those foods that contain both water-soluble and fat-soluble vitamins. Each food name should be listed only once. (7komplex)

8. Create a report to display the food names containing the different vitamins. The report should be grouped and ordered by the vitamin names. The food names should be in alphabetical order. If necessary, you can create auxiliary queries. (8jel)

9. List those vitamins to which there is no corresponding food in the database. (9hiany)

10. Create a crosstab query to give which vitamins are contained in the different food types (in the example, élelmiszer'' is food). (10kereszt)

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

(10 pont)

solution (in Hungarian), statistics

I. 285. Many of us know about the Logo programming language, in which we can create nice figures by controlling a turtle. The Imagine Logo programming environment is freely downloadable from http://logo.sulinet.hu. Your task now is to teach the turtle to draw a maze and to find its way out of a maze.

First create and draw a random maze on a square grid. The building blocks of each passage and wall are 11×11 squares: this square is either white (passage) or black (wall). The procedure creating the maze is called labkész :n :m with two parameters being the number of horizontal and vertical squares of the maze (n and m are odd integers). The centre of the maze should be in the centre of the Logo sheet. The only exit should be located just below the top left square.

The turtle perceives the color of the actual point on the sheet. With the aid of this, you should create a procedure called elhelyez :n :m, which puts the turtle randomly in the centre of a passage square. The turtle should head north. You should also create a procedure kitalál :n :m, which tries to lead the turtle out of the maze. The turtle should leave a colored trail (being 5 units wide) to show the passages already passed. However, a trail should not be drawn when the turtle is moving just inside a square. The procedure should end if the turtle left the maze.

The algorithm to find the exit can be very simple, it is not required that the turtle should solve any maze. Mazes without loops can be solved, for example, by moving the turtle to have walls always to the right of it.

In your solution you should only use turtle graphics and the functional part of the Logo language. Do not use variables, repetition should be carried out only by recursion. Divide your solution into procedures and functions which are useful on their own, e.g., drawing a square, or determining whether there is a wall in front of the turtle.

You should submit your solution -- as an i285.imp (Imagine Logo Project format) file and as an i285.txt file containing brief descriptions about your procedures and functions -- in a compressed file i285.zip.

(10 pont)

solution (in Hungarian), statistics

## Problems with sign 'S'

Deadline expired on February 10, 2012.

S. 68. One method to compress data is Huffman coding. In problem I. 276, you had to make a presentation about the coding process. Now you have to create a program to do the Huffman coding.

The Huffman coding replaces each byte of the original file with a sequence of bits of variable length: less frequent bytes will be replaced by longer, whereas more frequent bytes by shorter bit sequences. To create the Huffman code, a binary tree should be created first according to the frequencies of the original bytes, then this tree should be traversed appropriately. The tree is built up as follows.

1. First, each byte is considered as an isolated node of the graph. The node has no branches. The value of the node is the frequency of the actual character.

2. Then the two nodes with the least frequencies are merged: they will be the left and right branches of a new node whose value is the sum of the frequencies of the original two nodes. Then the original two nodes are deleted.

3. The previous step is repeated until only one node remains.

Now the Huffman code of a character is obtained by walking from the root to the actual character: each left step is a 0, while a right step is a 1 bit.

Your program s68 should create a possible Huffman code. The first command line argument is the name of the input file to be encoded. The second command line argument is the name of the output text file: each line should contain the sequence of bits (and their length) corresponding to each original byte. Lines of the output should be sorted according to the length of the bit sequences, then according to alphabetical order of the original bytes, as in the example. Non-printable ASCII characters and the space character should be displayed as their corresponding ASCII codes. Your program should also display the length in bits of the original file and the encoded file on the standard output.

In the table, Bemeneti állomány'' is the input file, Kimeneti állomány'' is the output file, Standard kimenet'' is the standard output, Eredeti hossz'' is the original length, while Kódolt hossz'' is the length of the encoded text.

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

(10 pont)

solution (in Hungarian), statistics

\$Var(Body)