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

KöMaL Problems in Informatics, September 2008

Please read the rules of the competition.

Show/hide problems of signs:

Problems with sign 'I'

Deadline expired on October 15, 2008.

I. 190. We simulate the crystallization of a melted substance in a rectangle-shaped furnace. The box is divided into N×M squares, containing either 0 (melted state) or 1 (crystallized state). A square with melted substance crystallizes, if at least 3 squares out of its 8 neighbours have already crystallized. See the figure.

The state of each square is recomputed in every simulation step, and we change melted into crystallized state where necessary. (In the next simulation step in the example, the middle 0 will become 1, because it has at least 3 crystallized neighbours. Similarly, the fourth cell in the first row will be 1, but no more changes will take place in this step.)

The command line argument of your program is the name of the input file containing the initial pattern of crystals. The first row of the input file contains two positive integers, the number of rows (3\leN\le200) and columns (3\leM\le200) of the state matrix. Then each of the following N lines contains M values, either 0 or 1.

The output of your program (written on the standard output) should contain the number of steps in which complete crystallization occurs. (If this does not happen, the output should be ``Crystallization has stopped''.)

See the example (``Bemenet'' is input, and ``Kimenet'' is output).

The source code of your program (i190.pas, i190.cpp, ...) together with a short documentation (i190.txt, i190.pdf, ...) should be submitted, also containing a brief description of your solution and the name of the developer environment to use.

(10 pont)

solution (in Hungarian), statistics

I. 191. John likes movies so he made a list of films he saw between February 1, 2001 and February 29, 2008. These are contained in the downloadable file mozadat.txt.

1. Prepare a database with name i191. Import the given table (containing titles of films, date of viewing, and ticket prices) with name moz_adat into your database. The text file is tabulator separated and field names are contained in the first line.

2. After importing, the appropriate data formats and a key should be set. A new identifier should also be created.

Now solve the following tasks and save the results with names given in parentheses.

3. Using a query, print all data of the films viewed on his birthday April 14 (3birthday).

4. Using a query, give those dates when more than one film has been viewed. The number of films should also be given (4morefilms).

5. Using a query, list the number of films watched in each month together with their prices. The list should contain the years, months, number of films and sum of ticket prices for every month (5monthlylist).

6. Using a query, determine those months between February 1, 2001 and February 29, 2008 in which John did not see any movie (6break).

7. Make a query that prints the film titles in alphabetical order if some part of the title is given as a parameter (7list).

8. List the film names that John saw more than once but at different prices (8different).

9. Using a query, determine what percentage of the films he watched during summer months (6th, 7th and 8th months) (9summer).

The database (i191.odb, i191.mdb, ...) or a text file (i191.txt, i191.pdf, ...) should be submitted containing the creation of the table and the queries in SQL-format arranged neatly, together with a short documentation (i191doc.txt, i191doc.pdf, ...) with the name and version number of the database manager.

(10 pont)

solution (in Hungarian), statistics

I. 192. Create a presentation about results of the Hungarian team at Beijing Olympic Games. The official logo of the Games should appear in the upper left corner of each slide, while a Hungarian flag in the upper right corner. In the lower part of the background image a podium should be visible.

Results of each day should appear on a separate slide containing Hungarian medals, one medal per line, in the upper part of the slide. The official logo of the sport, its name, the event, name(s) of the contestant(s), and type of the medal should be visible in each line, further, a photo of the contestant or team should also be placed appropriately on the podium. For example, the August 11th or the August 24th slide should include the following lines (with a photo of Cseh László on the second step of the podium and the photo of the Hungarian water polo team on the first step of the podium), respectively:

Lines with different events should appear with 1-2 seconds delay. After 4-5 seconds of the last contestant of that day the next slide should follow automatically. The photos and images can also be downloaded from the official website of the Games. You should present only those days during which the Hungarian team was awarded a medal.

The total number of Hungarian gold, silver and bronze medals should be displayed on the steps of the podium on the last slide.

Your presentation (i192.ppt, i192.odp, ...) together with a short documentation (i192.txt, i192.pdf, ...) should be submitted, also describing the name and version number of the software used.

(10 pont)

solution (in Hungarian), statistics

Problems with sign 'S'

Deadline expired on October 15, 2008.

S. 37. A Semiconductor Manufacturing Company plans to introduce dual-core processors.

They want to apply the following well-established method: instead of classifying new processors into predetermined speed ranges, they measure for each processor the highest clock speed at which it can safely operate in the long run, and sell the processor at this speed. Since the quality of new cores varies considerably, the company sells processors with rather different clock speeds.

The new dual-core processor of this company essentially consists of two single-core processors on one chip. Although the maximal clock speeds of single-core processors differ, the pair can only be operated at the same frequency: at the minimum of two frequencies. Therefore, for economical reasons, the maximal frequencies within a pair should not differ much.

Write a program that matches the maximal number of cores such that the difference of the maximal clock speeds of the two cores within a pair is less than a certain threshold. The maximal clock speed of each processor is found in the input file (specified as the first command line argument), and the result of your program should also be written into a file (specified as the second command line argument).

The first line of the input file contains two integers separated by a space: the number of cores

(0\le N\le 10\;000\;000) and the threshold (0\leT\le1000). The each of the following N lines contains a single integer: the maximal frequency 1\le F_i \le 10\;000 of core i is in row i+1. The first line of the output file should contain the maximal number of possible pairs, P, while the following P lines should have the number of the two cores, separated by a space. The order of pairs is arbitrary, and any solutions can be listed, if there are more than one.

In the example in the table, ``Példa Bemenet'' is input, while ``Példa Kimenet'' is output.

The source code of your program (s37.pas, s37.cpp, ...) together with a short documentation (s37.txt, s37.pdf, ...) should be submitted, also containing a brief description of your solution and the name of the developer environment to use.

(10 pont)

solution (in Hungarian), statistics


Upload your solutions above