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

KöMaL Problems in Informatics, January 2007

Please read the rules of the competition.

Show/hide problems of signs:

Problems with sign 'I'

Deadline expired on February 15, 2007.

I. 148. Members of a certain class give Christmas presents to one another in the following way: everybody prepares similar-looking boxes for everyone else with a student's name printed on each. Every gift box contains different items (repetition is possible), but there is at least one unique item in each box. (For example, Pete packs one bar of chocolate and one toy car into each box, Johnny packs one book and one pen, while Cecil packs one bar of chocolate and one book, etc.) Of course, no one gives a present to him- or herself.

After the celebration they would like to figure out who gave which present, so they list their new presents in a worksheet. Your task is to prepare a worksheet that prints on a different worksheet who gave which present.

The first two cells of the first row of the first worksheet contain the number of students N (1<N<40) and the number of different items M (1<M<100). Beginning with the second row, the first worksheet is structured as follows: every row corresponds to a student and every column corresponds to an item, while a cell in a certain column and row says how many items of that kind the others gave to the actual student. Your solution should be placed onto the second worksheet in a similar format: a cell in a certain column and row should say how many items of that kind the actual student gave to the others. Invalid cells should be left blank.

The sheet (i148.xls, ...) is to be submitted.

(10 pont)

solution (in Hungarian), statistics

I. 149. Make a presentation on members of the EU and its enlargement from the Maastricht Treaty November 1, 1993 until January 2007. The presentation is based on a black and white blank map of Europe with only state borders. In consecutive frames first the founding members, then the invited members should be marked one by one, together with the name of the country, capital city and date of admission. The colour of the 12 founding states is dark blue, that of later members is blue, while members joining in the beginning of 2007 should be light blue.

You should submit the presentation (I149.ppt, ...).

(10 pont)

solution (in Hungarian), statistics

I. 150. There are N cars (a few hundred) waiting at a traffic lamp. The lamp shows green for 45 seconds, then red for 15 seconds. Make a program to graphically simulate cars crossing the intersection. Cars are depicted as rectangles: the shorter side (width) has a constant length, while the longer side (length) has a random length. The acceleration is inversely proportional with the length of the car. The shortest car has length of 2 meters and accelerates to 100 km/h in 4 seconds, while the longest one has length of 20 meters and accelerates to this speed in one minute. The first car at the traffic lamp starts immediately when the green signal appears, with its maximal acceleration, until it reaches the maximal allowed speed (50 km/h). The next car starts after 1 second and accelerates according to its preset parameters (but its acceleration can not exceed that of the first car). If a car approaches another car within 20 meters, it immediately brakes and stops exactly 2 meters behind the first car. If the traffic lamp changes to red when the car is already within stopping distance (20 meters), then the vehicle proceeds further and crosses the intersection. Otherwise, if the car has enough time, then it brakes immediately and stops exactly at the lamp. You should update the position of the cars in every second. A car disappears when it has crossed the intersection, while the other cars behind it appear gradually until the queue of cars disappears. (The random length of this queue is determined in advance.) Cars in front of the traffic lamp should fill approximately 80% of the screen, while cars that have already crossed the intersection should occupy the remaining 20%.

The source code with appropriate documentation should be submitted.

(10 pont)

solution (in Hungarian), statistics

Problems with sign 'S'

Deadline expired on February 15, 2007.

S. 23. The table below shows file names and locations of their fragments on a hard drive:

1. weather.txt 160 0
2. --- 17 5
3. tale.doc 180 0
4. --- 20 2
5. --- 5 10
6. tale.doc 28 3
7. snow 128 0
8. santa.jpg 560 0
9. snow 47 7
10. --- 633 0

Rows of the table (at most 100000) represent consecutive areas of the hard drive (possibly of different size). Each row of the table contains the following information: either the name of the file or three dashes (the first numbers in each row of the example are there for easier readability only, so they are not part of the file names).

The file name consists of small letters of the English alphabet, and possibly a dot. The three dashes represent free space on the drive. After the file name or the dashes a space character follows, then the size of the file fragment or the free space (an integer between 1 and 100000). Then again a space character stands, finally an integer representing the location of the next fragment of the file in the table (being a positive integer, or 0, if this is the end of the file or the free space).

Write your program that sorts alphabetically the file names and the free space on the drive. The file name should be given first, then its total size, finally the starting and ending segments of the fragments of the file in the correct order separated by a dash. (All of these pieces of information are separated by space characters.) So in our example the output should be

snow 175 1099-1145 411-538
weather.txt 160 1-160
tale.doc 208 383-410 178-357
santa.jpg 560 539-1098
--- free space 675 358-377 161-177 378-382 1046-1078

Your program reads names of the input and output files from the command line, for example, s23.exe input.txt output.txt. The input file has a similar structure as in the example (but without the leading ordinal numbers). Your program will be tested thoroughly (with several thousand files on the virtual hard drive) and is expected to yield the final result within a few minutes.

Your source code (S23.pas, S23.cpp, ...) and a short documentation (S23.txt, S23.pdf, ...) should be submitted.

(10 pont)

solution (in Hungarian), statistics


Upload your solutions above