KöMaL Problems in Informatics, October 2006
Please read the rules of the competition.
Show/hide problems of signs:
Problems with sign 'I'
Deadline expired on November 15, 2006.
I. 139. The flow of a wide river increases quadratically from the bank to its center. Create an animation of a boat crossing this wide river, provided that travellers row steadily and always perpendicular to the bank. The GIF animation should consist of 25 frames.
A compressed file (i139.zip) should be submitted containing the GIF animation, a short description of your solution in plain text format and your source code files.
I. 140. Prepare a program to simulate falling characters on the screen. Your program should read the initial state from a file and print this text on the screen. Then in every tenth of a second a random character should be chosen and moved one line below, replacing the original position of the letter with a space. A letter can not fall further down if there is a non-space character just below it or if it hit the bottom of the screen.
The name of the input file is i140.txt. The file contains 25 lines, each line has 80 characters containing only letters, spaces or numerals.
The simulation ends when no more characters can fall. Your program then should print the message ``Every character has fallen off'' in the upper left corner and wait for Enter to be pressed.
The source code (i140.pas, i140.cpp, ...) should be submitted.
I. 141. Create an Excel sheet to help compare different tariffs of a mobile phone provider. The user should be able to set some parameter values on the first worksheet about the type of calls:
- most frequent hours of calls (from -- to)
- percentage of total calls within this time interval
- percentage of total calls within the given network
- duration of calls: at least and at most how many seconds.
Three tariffs should be compared with the following parameters:
- billing unit: one minute, half minute or seconds
- peak hours (from which hour to which hour)
- unit fee for calling within the network in peak hours and in off peak hours
- unit fee for calling outside the network in peak hours and in off peak hours.
To perform computations, you should generate a second worksheet with 1000 random calls using the parameters on the first worksheet. Determine the total cost of calls in each of the three tariffs and print the cheapest one on the first worksheet.
An example of a tariff: billing unit is half minute, peak hours are from 10 to 16, fees within the network in peak hours is 20 HUF, 30 HUF outside the network for half minute. 11 HUF in off peak hours within and 19 HUF outside the network.
An example of types of calls: most frequent hours from 11 to 18 and 80% of the calls take place in this interval. Duration of calls is between 18 and 175 second. 45% of the calls are within the given network.
The Excel sheet should be submitted with arbitrary parameters. We will also evaluate the user-friendliness of your sheet: the way one can enter parameters, and how cells are formatted and protected.
Problems with sign 'S'
Deadline expired on November 15, 2006.
S. 20. Your task is to find a smallest circle that covers n given points in the plane.
Each line of the input text file will contain the X and Y coordinates of a point in the plane, separated by a space. The coordinates are real numbers and may contain decimal points. The input file has no empty lines, the number of lines in the file is equal to the number of points in the plane. The name of the input file is specified in the command line, for example, as
Your program sends a single line containing the coordinates of the centre of the circle and its radius to the standard output. Data sets having at most 10000 points will be used for testing and evaluating your programs. Speed is also an important factor, an average solution should take no longer than a few minutes.
An example of the data.txt file:
The output in this case is
20.0 6.0 4.0
The source code (s20.pas, s20.cpp, ...) is to be submitted with a short documentation (s20.txt, s20.pdf, ...). (Without any documentation, at most 7 points can be awarded.)
Upload your solutions above