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

KöMaL Problems in Informatics, November 2013

Please read the rules of the competition.


Show/hide problems of signs:


Problems with sign 'I'

Deadline expired on December 10, 2013.


I. 331. Ancient Egyptians expressed (almost all) fractions as a sum of simple fractions with unit numerator. For example, 3/8 was given as 1/4+1/8 on Egyptian papyruses; they did not use the trivial but longer 1/8+1/8+1/8 form. In addition, they tried to express every operation with the help of addition and subtraction. Instead of multiplication and division, they used doubling and halving most of the time. As an example, let us consider how they computed ``13 multiplied by 17''.

The right column should be read from bottom to top, so the result is 136+68+17=221.

Performing the division of two integers was not a simple task either, as our next example illustrates. According to their papyruses, they computed ``62 divided by 13'' as follows.

Now they had to compute ``10 divided by 13'', which was performed by repeated halving. The right column in the next table should be read from top to bottom.

The last step is to answer that 1/4 is ``which number multiplied by 13''. So they considered the successive halves of 1/13:

The result of 62/13 is therefore 4+1/2+1/4+1/52. Since the numerator of each fraction is 1, this last form can be shortened and they simply wrote 4 /2 /4 /52.

You can find more information on Egyptian fractions and Egyptian algorithms on the Internet; in Hungarian, for example, in the book of Márton Sain (Nincs királyi út) from the Hungarian Electronic Library.

Your program i331 should perform multiplication or division of two positive integers below one million by using the Egyptian algorithm and format described above. Your program should process each line of the input file (given as the first command line argument to your program), and write the results (one result per line) into a file specified by the second command line argument. In the last table, ``Példa bemenet'' is a sample input, and ``Példa kimenet'' is the corresponding output.

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

(10 pont)

solution (in Hungarian), statistics


I. 332. Data for the biggest trees in Hungary have been collected for more than 10 years in public databases (see, for example, http://www.dendromania.hu/index.php?old=foold). They contain the name of the species of the tree, its perimeter, the geographical coordinates and the year it was put in the database. Data from Somogy county are contained in the file fa.txt. The file hely.txt contains location information as the name and population of the corresponding nearby settlements. Both files can be downloaded from our webpage.

1. Create a new database named somogyifak. Import the files fa.txt and hely.txt with table names fa and hely into the database. The files are UTF-8 encoded, tabulator separated text files, with field names in their first lines. You should add a unique identifier with name id to the table fa, and set the appropriate types and keys.

The queries and the report in the solutions of the following tasks should be saved as specified by the names in parentheses. Only the requested fields should appear in the queries.

2. Make a query to display (in alphabetical order) the name of the species and the perimeter for trees with perimeter between 7 and 9 meters. (2vastag)

3. The size of forested areas and hence the number of large trees greatly vary from settlement to settlement. List by using a query the number of trees in the database for each settlement. (3feljegyzesek)

4. Create a query to determine the number of oak trees in the database for each settlement. The name of the settlement should also appear, and the list should be sorted in decreasing order according to the number of trees. If two settlements contain the same number of oaks, alphabetical order is used. (4tolgy)

5. For the tree with the largest perimeter in the database and by using a query, display its species name, perimeter, its year of recording and the name of its settlement. (5kover)

6. A certain species, ``barkócaberkenye'' (Sorbus torminalis) was chosen to be the ``Tree of the year'' in Hungary in 2000. By using a query, display the names of the species living in the same settlement as ``barkócaberkenye''. Every species should appear once in your list, but the name ``barkócaberkenye'' itself should not. (6berkenye)

7. There can be settlements with several notable trees. By using a query, display the settlements having more than 5 different tree species in their record. The name of the settlement, its population and the number of species should be included. The list should be sorted in decreasing order according to the number of species. (7gazdag)

8. By using a query, list (in alphabetical order) the settlement names simultaneously having oak and beech trees. Each settlement should appear once. (8egyszerre)

9. Create a parametric query to display the species name, perimeter and settlement name of the tree nearest to the point given on the map by longitude and latitude in minutes. Instead of spherical coordinates, the usual planar coordinates should be used (the distance between two points (x1,y1) and (x2,y2) is d=\sqrt{{(x_{2}-x_{1})}^{2} +{(y_{2}-y_{1})}^{2}},\! and differences between elevations should be ignored. The table contains a sample input (``Bemenet'') and the corresponding output (``Kimenet''); notice that the decimal separator is the ``comma''. (9kereso)

10. Create a report to display settlement names in Somogy county with huge fir trees (``Fenyők listája'' in the example). The report should contain the name of the settlement (``Település''), the name of the species (``Faj'') and the perimeter (``Körméret''). The list should be sorted according to the name of the settlements, and for each settlement, smaller trees should be listed first. The report should be made by using queries containing the appropriate fields, or by auxiliary tables. The text and the order of the fields in your report should be similar to the example; the formatting can be different. (10fenyo)

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

Downloadable files: fa.txt, hely.txt.

(10 pont)

solution (in Hungarian), statistics


I. 333. Many of us like playing with soap bubbles, and several interesting phenomena can be observed on the boundary film of the bubbles.

By using a gif animation editor, animate the motion of a stick figure blowing bubbles. We recommend using the (freely downloadable) programs Stykz or Pivot Stickfigure Animator. A short description of these programs is found (in Hungarian) at http://blog.sulinet.hu/oktinf/category/palcikaanimacio/ and video tutorials on the usual video sharing sites.

Your animation - as realistic as possible - should contain the process of blowing a bubble, and the motion of the bubbles. For example, to create a bubble floating away, you can also move the background appropriately.

The animation should loop continuously and appropriate frame speed should be set.

The animation in gif format and its source code in the default file format of the editor should be submitted (i333.zip). A short documentation (i333.txt, i333.pdf, ...) with a brief description of your solution and the name of the animation editor should also be included in the compressed file.

(10 pont)

solution (in Hungarian), statistics


Problems with sign 'S'

Deadline expired on December 10, 2013.


S. 84. Pete and his brother play the following game. Pete asks his brother to think of a sequence of distinct positive integers with N terms. His brother then encodes this sequence as follows. The number at the i^{\mathrm{th}} position is replaced by a number c, where c is the length of the longest strictly increasing subsequence of the original sequence with the last term of the subsequence being the i^{\mathrm{th}} element of the original sequence (but elements of the subsequence are not necessarily consecutive elements of the original sequence). For example, if the original sequence is 3 1 2 4 8 20 10, then its encoded version is 1 1 2 3 4 5 5. The brother tells Pete the encoded sequence. Pete's task is to find a sequence such that its encoded version would be identical to the one he got from his brother. Your program should help Pete's task.

Your program should read the value of N (N\le 500\;000) from the first line of the standard input, then the terms of the encoded sequence (integers separated by a space) from the next line. The first and only line of the standard output should contain a sequence (consisting of N positive integers) whose encoded version is the input sequence. Since there are multiple solutions in general, it is enough to display one. Numbers in the input are bounded by 10000000 from above, and this bound should also hold for numbers in the output. The output should consist of distinct integers.

In the example, a sample input (``Példa bemenet'') and the corresponding output (``Példa kimenet'') is displayed.

Scoring and bounds. You can obtain 1 point for a brief and proper documentation clearly describing your solution; 9 further points can be obtained provided that your program solves any arbitrary valid input within 1 second of running time. Partial points can be obtained if your program yields a solution for N\le5 or N\le500.

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

(10 pont)

solution (in Hungarian), statistics


$Var(Body)

Upload your solutions above