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

KöMaL Problems in Informatics, March 2013

Please read the rules of the competition.


Show/hide problems of signs:


Problems with sign 'I'

Deadline expired on April 10, 2013.


I. 316. Elementary statements of a logical expression are denoted by uppercase letters of the English alphabet. A logical expression may contain the not, and, or and the implication operations, denoted by the characters !, &, | and >, respectively. Parentheses are used modify the precedence, if necessary.

Your program should illustrate the evaluation of such expressions in the following way. First, choose one part of the expression that is among the expressions to be evaluated first, and denote it by a lowercase letter of the English alphabet. Then substitute this letter into the original expression, and repeat the above procedure over and over again. At the end, we obtain only one lowercase letter of the English alphabet.

The only line of the input file contains the logical expression to be processed, with a maximal length of 80 characters. Successive lines of the output file should show the steps of the evaluation process. Each line consists of 2 parts: the first part begins with a still unused lowercase letter of the English alphabet, then an equality sign should be displayed, finally, a subexpression to be evaluated first is shown. The second part comes after a space character: the original expression should be rewritten so that the subexpression to be evaluated has been replaced by the actual lower case letter.

The table shows some inputs (``Bemenet'') and the corresponding outputs (``Kimenet'').

The first and second command line arguments to your program should be the name of the input and output files, respectively.

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

(10 pont)

solution (in Hungarian), statistics


I. 317. The Hungarian Central Statistical Office (abbreviated as KSH in Hungarian) publishes some basic data on settlements in Hungary each year. In our exercise I305, you had to create a database based on their report made available on January 1, 2011. Queries in the current exercise should use the same data. We again remark that it contains data for the capital city as well, however, not as a whole city, rather than data for each of its districts.

1. You should create an empty database i317. You should import data into the tables helyseg, kisterseg, megye, megyeresz, onkormanyzat, telepulestipus, kisebbseg from the text files with similar names. (The text files are UTF-8 encoded and tabulator separated with first lines containing the field identifiers.) The relations among the tables are shown in the figure.

Tables:

2. Create a query to give those cities with county rights that are not county seats, together with their county names. (2megyeijoguvarosok)

3. Create a query to list the district of the capital city having the smallest number of minority governments, and how many. (3keveskisebbseg)

4. Give the name, region name and county name of those settlements that contain the string ``magyar'' (= Hungarian) somewhere in their name. (4magyarok)

5. By creating a query, give the name, county name and the number of their settlements together with their total population of the regions that have more than 20 settlements. The list should be sorted according to the county names. (5nagykistersegek)

6. List by a query which minority has no local government in any settlement in county Heves. (6hevesbennincs)

7. How many percent of people in Hungary live in cities? Besides cities, you should also take into account people living in cities with county rights, in county seats, moreover, in districts of the capital city. (7varoslakok)

8. Give by a query the number of cities in each county, and the number of districts in the capital city. Again, besides cities themselves, cities with county rights and county seats should be counted here as well. (8varosszam)

9. For each county, determine the average number of persons living in one household in each of the different settlement types. (9lakok)

10. Give the name of those counties in which more than 50% of the people live in villages. (10falusitobbseg)

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

(10 pont)

solution (in Hungarian), statistics


I. 318. Sheet music is used to represent notes, rhythms, songs and related information. They are issued by music or book publishers in a printed form. Due to various royalties and the limited number of editions, their price is typically high. However, one can find high quality music sheets on the Internet, as the example illustrates.

Your task is to create a music sheet for a popular song. You may want to use the freely downloadable software MuseScore. (Known video sharing sites or the pages below http://musescore.org contain information or tutorials on the program and its usage.) The program can even play the completed sheet by its sound synthesizer.

As a source, you can use Internet- or paper-based sheets or issues. The music genre should be popular music, but otherwise arbitrary. The length of the sheet should be between 3 staves and 2 pages.

Your sheet music should be submitted in the default file format of the editor (mscz) in a compressed file i318.zip, also containing a short documentation (i318.txt, i318.pdf, ...) with an accurate reference or link to the original work used.

(10 pont)

solution (in Hungarian), statistics


Problems with sign 'S'

Deadline expired on April 10, 2013.


S. 79. We are given a weighted graph on N points and M edges with N\le 100\;000 and M\le 100\;000. For each edge e, decide whether there exists a minimal spanning tree containing e. A minimal spanning tree by definition is a spanning tree with the smallest total weight; a spanning tree is a tree that contains all the vertices of the graph together with some edges; and a tree is a graph without a (simple) cycle. A minimal spanning tree is said to contain e, if it is a minimal spanning tree with one edge being e.

Your program should read the values of N and M from the first line of the standard input, then the integers ki, vi and si (each separated by a space character) from the next M lines: ki and vi denote the endpoints of the ith edge with weight si. The ith line of the standard output should contain the word ``Igen'' (= yes), if there is a minimal spanning tree that contains the ith edge, and the word ``Nem'' (= no), if no such tree exists.

The table shows a sample input (``Példa bemenet'') together with the corresponding output (``Példa kimenet'').

Scoring and bounds. You can obtain 1 point for a brief and proper documentation clearly describing your solution. The maximal 9 points for your program can only be obtained if it can solve an arbitrary valid input within 1 second of running time. Partial points out of the 9 points can be obtained if your program can solve only smaller test cases within the allotted time, according to the following bounds:

\bullet 2 points for 0<M\le300;

\bullet 3 more points for 300< M\le 2\;000;

\bullet finally, 4 more points for the cases 2\;000< M\le
100\;000.

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

(10 pont)

solution (in Hungarian), statistics


$Var(Body)

Upload your solutions above