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 2011

Please read the rules of the competition.


Show/hide problems of signs:


Problems with sign 'I'

Deadline expired on October 10, 2011.


I. 271. In this exercise you are going to model percolation--a phenomenon when a liquid passes through a solid (but porous) substance. Your program i271should run the simulation on a grid of n×n squares (1\len\le500), representing a vertical cross section of the solid material. The liquid can pass through each cell with probability p (0.00\lep\le1.00), say, through a microscopic crack, and can not pass with probability 1-p.

A liquid can not pass through the material in first figure in the example, but can pass from top to bottom in the second figure: darker cells allow percolation. The liquid can move from a cell to its bottom left, bottom or bottom right neighbor.

Create a statistics to count how many times the liquid could percolate through the solid material, as the parameter p is varied.

To do this, first fix an arbitrary n (between the given lower and upper bounds) -- in the documentation, this side length n should also have the same value. Then, for each p, generate at least 100 random grids and count how many times a liquid could pass through the given material. Let us call this number per. (Then, clearly, 0\le per\le \mbox{number} of grids with the given p.) Finally, the (p,per) pairs should be written into a text file, and displayed on a PointXY diagram using a spreadsheet application.

The source code of your program (i271.pas, i271.cpp, ...), the spreadsheet (i271.xls, i271.ods, ...) containing the diagram, further, a brief description of your solution (i271.txt, i271.pdf, ...) and the name of the developer environment to use for compiling the source file should be submitted in a compressed file i271.zip.

(10 pont)

solution (in Hungarian), statistics


I. 272. For a sports magazine we have collected some data about Formula 1 pilots. Since we used English-language sources, some conversions may be necessary before you can make a statistics for the magazine.

1. Import the tabulator separated text file adat.txt into the spreadsheet versenyző (pilot) and save it as forma1 in the default format of the spreadsheet application. The text file is downloadable from our homepage.

2. Column D should contain the name of the pilot as ``Zsolt Baumgartner (Hungary)''.

The editor of the magazine requests names to be sorted according to ascending birth dates, so you have to calculate the date of birth in column E. In order to do this, you should process data in column C as described below. (If necessary, you can make some auxiliary computations or create some auxiliary tables right to column J.)

3. Determine the pilot's birth year in column F.

4. Determine the month of birth in column G.

5. Determine the day of birth in column H.

6. Determine the birth date in column E in the following format: ``1981 January 1''.

7. Pilot data should be sorted according to ascending birth dates.

8. Insert a new sheet ország (country) into the spreadsheet. In its column A, list all countries that have or had a Formula 1 pilot. Column B should contain the number of such countries.

9. Country data for countries giving at least 15 pilots should be displayed on a two-dimensional bar chart. The scale should begin with number 10, and the color of a bar should be the flag of the actual country.

10. The editor wishes to present a pilot on each day of the year, having birthday on that day. Therefore, you should create a new sheet nap (day).

11. Column A of sheet nap should contain the days of the year from January 1 to December 31. The name of the month and the number of the day should be visible in each cell.

12. Column B of sheet nap should contain the number of pilots having birthday on that particular day. You are allowed to use auxiliary cells on sheet versenyző or on sheet nap.

Your spreadsheet (i272.xls, i272.ods, ...) together with a short documentation (i272.txt, i272.pdf, ...) -- also describing the name and version number of the spreadsheet application -- should be submitted in a compressed file i272.zip.

(10 pont)

solution (in Hungarian), statistics


I. 273. Several episodes of the well-known Hungarian folk tales (Magyar népmesék) can be found on popular video sharing sites. You should select one of these tales and create a slideshow to be presented on a web page. Each slide is an image below which some sentences (with white letters on a black background) about the story are displayed. The web page should be able to play the slideshow similarly to a slide projector. You can use any web tools that also work offline, e.g. Javascript or Flash. You should pay attention to the content, further, the format should resemble to that of a slide projector as much as possible.

The only HTML document of the web page i273.html, the corresponding images, auxiliary files and a description of your solution (i273.txt, i273.pdf, ...) together with the source of the film should be submitted in a single compressed file i273.zip.

(10 pont)

solution (in Hungarian), statistics


Problems with sign 'S'

Deadline expired on October 10, 2011.


S. 64. The position of K elements is given in an array of length N. These elements are deleted one after another from the array. As usual in the context of arrays, after performing a deletion, elements following the actually deleted element are shifted back by one position, so the position of the next element to be deleted is understood relative to the new array, see the example.

Your program should determine the sum of the elements in the final array of length N-K, if the original array and a list of positions to be deleted are given.

The first line of the standard input contains two integers separated by a space: the length of the original array 1\le N\le 1\;000\;000, and the number of elements 0\leK\leN to be deleted. The second line of the input contains the original elements of the array x1,x2,...,xN (0\lexj\le232-1, integers), again, separated by a space, while the third line of the input the indices i1,i2,...,iK (1\leik\leN-k+1) to be deleted.

The only line of the standard output should be a single number: the sum of the elements of the array after deletion.

In the example, ,,Példa bemenet'' is the sample input, ,,Példa kimenet'' is the output, and ,,Lépések'' is steps.

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

(10 pont)

solution (in Hungarian), statistics


$Var(Body)

Upload your solutions above