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

# KöMaL Problems in Informatics, May 2010

Show/hide problems of signs:

## Problems with sign 'I'

Deadline expired on June 10, 2010.

I. 241. In certain quizzes contestants have to find one or more strings on a board of letters. We know that cells of consecutive letters in a word always have a common edge, further, no letter can be repeated within one word.

The first command line argument to your program is the name of the file containing the character table to be searched. The first line of this file contains the size of the board (number of lines and columns, separated by a space), further lines then contain the actual characters (with a space character between them). The number of lines and columns are at most 10, characters are lowercase letters from the English alphabet.

The second command line argument to your program is the name of the file containing the words to be found. The first line contains the number of strings. Strings (of length at most 30 characters, one string per line) themselves are found in the next several lines. There are at most 20 strings, comprising lowercase letters from the English alphabet.

The third command line argument to your program is the name of the file to be created. This file should contain the strings found in the board. The word list file (that is, the file given by the second command line argument) should specify the order of the strings and corresponding modified boards appearing in the third file. Strings found should be highlighted by uppercase letters. If a string occurs more than once, you should give exactly one (but an arbitrary) occurrence. Solutions should be separated by exactly one empty line.

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 (i241.txt, i241.pdf, ...) in a compressed folder i241.zip.

The sample files tablazat.txt (the character table), szavak.txt (the words to be found) and eredmeny.txt (the results) contain some simple examples.

tablazat.txt

5 7

z v c a e l c

a a s c y x d

k k a l c l l

d o m a t e k

l w a q w l w

szavak.txt

2

matek

komal

eredmeny.txt

matek

z v c a e l c

a a s c y x d

k k a l c l l

d o M A T E K

l w a q w l w

komal

z v c a e l c

a a s c y x d

k K A L c l l

d O M a t e k

l w a q w l w

(10 pont)

solution (in Hungarian), statistics

I. 242. In problem I. 237 you created a data table of the 185-year-old Hungarian Academy of Sciences. After processing these tables, a list of members in 2007 together with some additional data is available in the files szemely.txt, kapcsolo.txt and foglalkozas.txt. These files are tabulator separated text files in UTF-8 encoding with field names in the first list.

[1.] Create a new data base named mta. The above 3 data files should be imported into the data base using the same names szemely, kapcsolo and foglalkozas.

[2.] Upon importing, you should set the appropriate data formats and keys. No new fields should be created in the tables.

The structure of the tables is the following:

szemely (id, nev, szul, nemzetiseg, tipus, mettol)

 id Identifier of the member of the Academy (number), this is the key; nev Name of the academician (text); szul Year of birth of the academician (number); nemzetiseg His or her nationality -- can be multiple (text); tipus Type of membership -- external, honorary, corresponding or full (text); mettol Starting year of the latest membership type (number);

kapcsolo (szemely_id, foglalkozas_id)

 szemely_id Personal identifier (number), key; foglalkozas_id Identifier of the occupation (number), key;

foglalkozas (id, nev)

 id Identifier of the occupation (number), this is the key; nev Name of the occupation (text)

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.] By using a query, list in alphabetical order the names and nationality of the mathematician academicians. (3matematikusok)

[4.] Make a query that counts the number of members for each membership type. (4tipusdb)

[5.] List in a decreasing order how many academicians pursue each occupation.\ (5szakmadb)

[6.] By using a query, give the name of the youngest full member and his or her age (at the moment of executing the query). (6fiatal)

[7.] By using a query, give the name of the academician who became a full member when he or she was the youngest, give his or her age at that time and what his or her occupation is. (7koran)

[8.] By using a query, give the other occupation(s) of the geologist academicians. Each occupation should appear only once in the list. (8geo)

[9.] List those people who have the same occupation as Vilmos Csányi. (9csanyi)

[10.] Hungarian scientists have the nationality rubric blank. By using a query, fill these up with the word ,,Hungarian''. (10magyar)

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

(10 pont)

solution (in Hungarian), statistics

I. 243. Optical illusions are created in the brain when inconsistent information is transmitted by the optic nerves. One peculiar example is the Münsterberg illusion, in which lower and upper edges of the parallel black and white squares seem to be bent and converge towards each other near the boundary.

Prepare your program that creates an SVG vector graphics file containing an image of the Münsterberg illusion after reading the parameters. Most browsers are able to display SVG files without any problem. The structure of an SVG file is described, for example, on the page http://svg.elte.hu/.

[--] $\displaystyle N$, being the number of horizontal and vertical black squares ($\displaystyle 3\le N\le 50$);

[--] OLDAL, being the side length of each square ($\displaystyle 5\le \text{OLDAL} \le 50$);

[--] VV, being the thickness of the horizontal separating lines ($\displaystyle 0\le \text{VV}\le \text{OLDAL}$);

[--] finally FAJLNEV, being the name of the image.

In the example (Példa bemenet az ábrához) you can see the parameters for the sample image.

 Példa bemenet az ábrához $\displaystyle N = 8$ $\displaystyle \mbox{OLDAL} = 30$ $\displaystyle \mbox{VV} = 2$ $\displaystyle \mbox{FAJLNEV} = \mbox{'optika.svg'}$

One can experience the strongest optical illusion if colour tones of the squares are rather different and the colour of the separator line is between theirs.

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

(10 pont)

solution (in Hungarian), statistics

## Problems with sign 'S'

Deadline expired on June 10, 2010.

S. 54. Nonograms, also known as Paint by Numbers or Griddlers are picture logic puzzles in which cells in a grid have to be colored or left blank according to numbers given at the side of the grid to reveal a hidden picture. In this puzzle type, the numbers measure how many unbroken lines of filled-in squares there are in any given row or column. For example, a clue of 4 8 3'' would mean there are sets of four, eight, and three filled squares, in that order, with at least one blank square between successive groups.

Source: http://en.wikipedia.org/wiki/Nonogram

In the example one should reveal a hidden digit 8''. (Feladat'' is the original puzzle, Megoldás'' is the solution, while Bemenet'' is the corresponding input.)

The structure of the input is the following: the first line contains 2 numbers, the number of rows (s25) and columns (o25) of the image. Then each of the following s lines describes one row of the image by specifying the length of consecutive black blocks of that row. Similarly, each of the next o lines describes the length of consecutive black blocks of the actual column. In the input file there is exactly one space between each piece of data.

Your program should read the description of the puzzle from the standard input, then write the solution image in s rows and o columns to the standard output. A black square is represented by an ,, X'' character and ,,.'' (dot) should be written otherwise.

Your program (s54.pas, s54.cpp, ...) together with a test case (s54.be) and a documentation (s54.txt, s54.pdf, ...) should be submitted. Your test case will also be used to test your other competitors as well.

Evaluation of solutions:

At most 6 points can be awarded if your program correctly solves the test cases created by the proposers of this problem. (The time limit for each test case is 1 minute on a Core2Duo processor at 2 GHz with 2 GB of memory.)

The documentation and your test case are worth of 2 points.

Finally, 2 more points are awarded if your program solves within the time limit the most test cases submitted by other contestants. If there is a draw, then solutions are ranked according to the total time needed to solve the test cases. Besides the winner, competitors ranked among the first half of all will be awarded 1 extra point.

(10 pont)

solution (in Hungarian), statistics

\$Var(Body)