KöMaL Problems in Informatics, November 2012

Problems with sign 'I' Deadline expired on December 10, 2012.

---

I. 304. Tom has created a counter based on a description he found on the Internet. According to this, the 3-digit counter should have counted from 0 to 999, increasing its value by one in every second. Something must have gone wrong, however, since the counter changed the states in every 1/10th of a second. Moreover, the liquid crystal display consisting of 7 segments did not always react to the control instantaneously: sometimes a segment updated its state normally at once as it should, but sometimes it stopped responding to the control for at most k tenth of a seconds. If, for example, k=2, then the activation of a dark segment may take place in the 0th, 1st, or in the 2nd tenth of a second. But it is also possible that the activation did not happen at all if the next ``off signal'' to the segment was executed earlier than the delayed ``on signal''.

Tom was wondering whether one could figure out the correct value (i.e. the one it displayed if there were no delay present) of the last digit without knowing the initial state and without stopping the counter. Although errors are encountered with different delays, he soon realized that the correct state of the last digit could be found out by inspecting sufficiently many previous states.

Write your program that determines the correct value of the last digit by knowing some previous successive states.

The first line of the input file contains the reaction time of the display (0k5, integer). The next line contains the number of successive previous states n (1n100). The following n lines then encode the state of the last digit of the display from the beginning of the observation and measured in tenth of a seconds. Each line describes the last digit of the display in the actual moment by giving the state of each segment (0 - off, 1 - on).

The output file should contain the number of states to be observed so that the correct value of the last digit could be figured out, further, the correct value of the last digit itself should be included. If the given time frame happens to be insufficient to unambiguously determine the correct value of the last digit, the output should be ``0''.

The first table with the figure tells us how digits from 0 to 9 are built up from the segments.

Then an example is given, showing an input (``Bemenet'') together with its corresponding output (``Kimenet'').

The explanation of the final figure is the following. The first row shows the 10 states of the last digit if no delay is present. The second row shows an example of 10 successive states of a digit if the delay is k=1. Black segments are lit (``on''), white segments are ``off'', while the state of the grey segments cannot be determined. The third row contains the first three states of the example ``Bemenet'', which are sufficient to uniquely determine the next correct value of the last digit.

The first command line argument to your program is the name of the input file, while the second argument is that of the output file.

The source code (i304.pas, i304.cpp, ...) together with a short documentation (i304.txt, i304.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. 305. The Hungarian Central Statistical Office (abbreviated as KSH in Hungarian and in this exercise) publishes some basic data on settlements in Hungary each year. This exercise is based on the report made available on January 1, 2011. We 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 i305. 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 names.) The relations among the tables are shown in the figure.

Tables:

[2.] Create a query listing settlements of the Kecskemét region and sorting them according to decreasing population. (2kecskemet)

[3.] Create a query giving the number of regions in each county. (The capital city should be ignored.) The list should be sorted according to county names in alphabetical order. (3kistersegek)

[4.] List by using a query the number of settlements of each type in Hungary. (4tipusok)

[5.] Create a query giving the number of square kilometers of the area of Budapest (). (5bpter)

[6.] By using a query, list settlements having an Armenian minority government.\ (6ormeny)

[7.] By using a query, give the number of settlements having at least 5 local minority governments. (7sokkisebbseg)

[8.] By using a query, give the names of the 30 most densely populated settlements, together with their population size and population density measured in people/hectare. (8suru)

[9.] How many settlements are there in each county whose names begin or coincide with one of the words of the name of its county? (9johelyen)

[10.] List those settlements whose names begin with one of the words of the name of another county. List the settlement name and its county name as well. (10máshol)

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

Downloadable file: i305forras.zip

(10 pont)

solution (in Hungarian), statistics

---

I. 306. Surveys, polls, reports - there are lots and lots of these documents: often the evaluation costs more than their creation. There are various programs to help processing these forms: some to make paper forms, some to help the digital processing, but most of them to collect data electronically. One can chose among these programs by taking into account the aim of collecting data and the target groups.

Your task is to demonstrate the use of a free electronic form management system. Possible application areas of the tool together with its limitations and its terms of use should all be highlighted.

As an illustration, you may use some pages of text with screenshots showing the process of creating, filling out and evaluating forms. As a concrete example, create a form consisting of 8-10 questions for your classmates or for solvers of the KöMaL. Your form should be clearly legible and have an appropriate design.

A document (i306.pdf) with the above content and a link pointing to the electronic form should be submitted.

(10 pont)

solution (in Hungarian), statistics

Problems with sign 'S' Deadline expired on December 10, 2012.

---

S. 75. We are given N intervals (at most 1000000) on the real line with starting points and endpoints (k_i,v_i), 1iN and . A set of intervals is referred to as proper, if for any pair of intervals from this set, one is contained in the other. (The interval (k_i,v_i) contains the interval (k_j,v_j), if k_ik_j and v_jv_i.) From an arbitrarily given set of intervals, your program should select a proper subset of intervals with maximal possible cardinality.

Your program should read the value of N from the first line of the standard input, then the values of the integers k_i and v_i (separated by a space) from the next N lines. The program should write the cardinality of the maximal proper subset of intervals to the standard output.

The example contains a sample input (``Példa bemenet'') with the corresponding output (``Példa kimenet'').

Scoring: 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 can be obtained if your program can solve only smaller test cases within the allotted time: the 9 points are then divided into the following parts.

1 point for the cases with 0<N150;

3 points for the cases with 200<N<2000;

5 points for the cases with .

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

(10 pont)

solution (in Hungarian), statistics