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 2011

Please read the rules of the competition.


Show/hide problems of signs:


Problems with sign 'I'

Deadline expired on December 12, 2011.


I. 277. The file helyforr.dat (downloadable from our webpage) contains the name, geographical coordinates and number of inhabitants of Hungarian settlements. Your program i277 should display these settlements on the screen as a point, or a circle/rectangle proportional to the settlement's population, if the population is larger than 10000, see in the example.

Your program reads the geographical coordinates, the number of inhabitants and the name of the settlement from a file. The first line of the file contains the number of settlements n together with the horizontal (dx) and vertical (dy) size of the rectangular map on the screen (256\ledx,dy\le1024). Then each of the following n lines contains data for the settlements. The first two pieces of data of the actual line are the longitudinal and latitudinal coordinates in minutes. The third quantity is the population, while the last piece of data is the name (without any diacritical marks), see in the example ``Példa a bemenetre''.

You should display all settlements in a rectangular box with sides dx and dy. The given spherical coordinates should be interpreted as ordinary planar coordinates X and Y. This way you will obtain the map of settlements of Hungary.

Settlements with population larger than 10000 should be highlighted with a circle or square. The centre of the highlight should coincide with the geographical coordinates. The size of the highlight should correspond to the size of the population. In the case of Budapest, having by far the largest population, you should individually choose the size of its highlight: it has to be 1.5 times the size of the highlight of the second largest city.

The source code (i277.pas, i277.cpp, ...) together with a short documentation of your program and solution (i277.txt, i277.pdf, ...) -- also specifying the name of the developer environment to use for compiling the source file -- should be submitted in a compressed file i277.zip.

(10 pont)

solution (in Hungarian), statistics


I. 278. Depletion of fossils fuels emphasizes the role of other sources of energy, such as water. River discharges and water levels have been measured for many decades. In this task you will analyze water levels of Danube in 2009 and 2010.

The tabulator separated text file vizallas.txt downloadable from our homepage contains data in UTF-8 encoding.

During your solution, you should, if possible,

-- use a formula, function or link

-- make auxiliary computations only below line 78, or to the right of column R.

1. Open the file vizallas.txt in a spreadsheet such that the first piece of data is displayed in cell A1. Save the sheet named i278 in the default format of the application. The first column of the sheet contains the years and days, while columns B:M contain the abbreviation of the months together with the corresponding water levels.

2. In cell E72, determine the number of months in which the average monthly levels in 2010 were higher than in 2009.

3. In cell E73, you should give the \(\displaystyle 10^{\rm th}\) highest water level in 2009. (It is possible that some measurements may have the same water levels.)

4. Cells E74:E75 should contain which year and month had the largest change in water level.

5. A certain boat can not start sailing if the water level is less than 200 cm. Cell E76 should contain the total number of such days during the sailing seasons between March 21 and October 15.

6. Cell P4 should contain an expression that determines the water level on a particular day based on the date written into cells P1, P2 and P3, or display the message ``Invalid date'' if there is no corresponding water level data. Cell P2 will contain the 3-letter abbreviation of the month similarly to the example.

For example, if P1: 2010, P2: ``FEB'' and P3: 11, then P4 should be 154.

If any of P1, P2 or P3 is empty, P4 should be empty too.

7. Create a diagram about water levels in July 2009 and 2010 according to the following:

\(\displaystyle a.\) The type should be a line diagram.

\(\displaystyle b.\) The diagram should appear on a new sheet.

\(\displaystyle c.\) Data corresponding to 2009 should have a thick red line, while that of 2010 should be in thick blue.

\(\displaystyle d.\) The monthly average water levels should be graphed as thin red (2009) and thin blue (2010) lines. If the data are changed, the diagram should follow those changes.

\(\displaystyle e.\) A legend should appear underneath, such as ``2009 July average'' or ``2010 July average''.

\(\displaystyle f.\) The title of the diagram should be ``Water levels in July''.

8. The text in cells containing years and months in the original sheet should be in bold and aligned in the center.

9. Background color for cells with computed values should be yellow.

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

(10 pont)

solution (in Hungarian), statistics


I. 279. The webpage www.facebook.com has multiple IP addresses changing from time to time. To see this, simply issue an nslookup www.facebook.com command from the command line several times, and you can get different results within a minute.

Create a statistics report to investigate this change of the IP address. You should use Linux operating system possibly on a machine that has continuous Internet connection. (To avoid installing Linux on a separate partition on your machine, you may want to use a Live system booting from a CD, see www.livecdlist.com, or a Linux version that can be installed within Windows, then simply removed, such as wubit or Ubuntu Linux.)

To begin collecting data, first create a shell script named facebook.sh. Your operating system should run this script every minute. By using Unix commands, your script should determine the actual IP address of www.facebook.com together with the date and time, then write these into the file facebook.out: each line of the file should contain the actual date and time, and the IP address, separated by tab characters, like 2011.10.16 \to 10:23 \to 213.46.246.53.

Then you should create the text file facebook.stat with your statistics, each line containing one IP address, the number of its occurrences, finally the average time (rounded to minutes) between two successive occurrences of the IP address. If a particular IP address has been used only once, this last value should be zero. Your file should be sorted according to increasing IP addresses, and values should be separated by tab characters. The file containing this statistics should be created by an fstat.sh script.

You are allowed to use only programs and scripts of the Linux operating system. If necessary, commands can create further files. You should collect and evaluate at least 4 hours of data.

You should submit the gzip compressed file i279.gz containing the requested scripts and text files, further, the file idozites.txt (``timing''), describing how you managed to run the appropriate script in every minute.

(10 pont)

solution (in Hungarian), statistics


Problems with sign 'S'

Deadline expired on December 12, 2011.


S. 66. Weird lightning strikes occur in Lightning City day by day: a lightning always blasts into 2 houses simultaneously. Inhabitants realized that they can make use of this phenomenon and cover the electric energy demand of the city by the following construction. They connect certain houses with (lightning-proof) electrical wirings in such a way that there is exactly one path between any two houses, moreover, they install a battery into each home with (effectively) infinite capacity: when a lightning strikes the two houses, all the batteries along the path between the two affected homes are charged evenly.

At the end of the month, the mayor needs a report about the amount of energy each home obtained from the lightning strikes. Your program is to create such a report, provided that the wiring paths between the homes, further the destination and energy of each strike are known.

The first row of the standard input contains the number of homes 1\leN\le50000, then each of the next N-1 lines contains the number of two homes (separated by a space) that are directly connected with a wire. The next line contains the number of lightning strikes 1\leQ\le50000. Then each of the following Q lines contains 3 integers (separated by a space): the destination homes Ai and Bi of the actual strike together with the additional energy 1\leCi\le100 each battery gets during this strike between homes Ai and Bi.

The standard output should contain exactly N lines: the ith line shows the total energy collected by the ith home during the month. In the example, ``Példa bemenet'' is a sample input, while ``Példa kimenet'' is the corresponding output.

In order to obtain the maximal number of points, your program should give the solution within 3 seconds even on the largest input.

The source code (s66.pas, s66.cpp, ...) and project files -- without the .exe or any other auxiliary files generated by the compiler but together with a short documentation (s66.txt, s66.pdf, ...) -- should be submitted in a compressed folder s66.zip.

(10 pont)

solution (in Hungarian), statistics


$Var(Body)

Upload your solutions above