KöMaL Problems in Informatics, September 2012
Please read the rules of the competition.
Show/hide problems of signs:
Problems with sign 'I'
Deadline expired on October 10, 2012.
I. 298. We are given an N×N billiard table with some point-like balls initially having integer coordinates within the table. When balls collide with the boundary, they are reflected in a perfectly elastic manner.
Your program i298 should determine and display on the standard output the number of ways a given ball starting from (k,l) can hit another selected ball located at (x,y).
We impose some simplifying assumptions on the path of the moving ball as follows: before hitting the target ball, it can collide with at most two walls, and it should not touch any third ball during its route. If the moving ball hits the corner of the table, then the outgoing trajectory will be the same as the incoming one and we count this as two wall collisions.
The output of your program is the number of possible paths grouped according to 2, 1 or 0 boundary collisions. The example shows 3 possible paths.
The command line input to your program is the name of the data file describing the initial conditions. The first line of the file contains the size of the board N (2N50) and the number of balls M (1<M20). The next M lines describe the coordinates of the balls, then coordinates of the source ball (k,l) (1k,lN) and the target ball (x,y) follow. The lower left corner of the table has coordinates (1,1) and the first coordinate increases to the right, while the second one upwards.
In the table ``Bemenet'' is a sample input referring to the figure, while ``Kimenet'' is the corresponding output. ``Ket/Egy/Nulla pattanas'' gives the number of boundary collisions: 2, 1 or 0.
The source code of your program (i298.pas, i298.cpp, ...) together with a short documentation (i298.txt, i298.pdf, ...) should be submitted, also containing a brief description of your solution and specifying the name of the developer environment to use for compiling the source code.
I. 299. A spice company has introduced a new product line consisting of spice mixes. The name of the mixes, their recipes and data of the basic ingredients are stored in a database.
The database consists of three tables:
The relation between the tables is illustrated by the figure.
Create a database i299 and import data from the UTF-8 encoded text files with the same names as the tables. Remember to define the appropriate relations.
Create your queries answering the following questions.
[1.] List the names of those mixes that contain curcuma. (01kurkuma)
[2.] Give the ingredients of the Sichuan mix, together with their relative amounts in descending order. (02szecsuani)
[3.] Give which mix contains the largest number of components together with this number. (03legtobbfele)
[4.] The company distributes 100 free product samples of each mix, all samples weighing 100 grams. Calculate the total price of the spices needed. (04mintaar)
[5.] Due to a ship accident the ingredients Sichuan pepper and cardamom are temporarily unavailable. List the names of the affected mixes whose production should be halted. Each mix name should appear at most once. (05nemkeverheto)
[6.] Under the assumptions of the previous question, list those mixes whose production can be continued without interruption. (06keverheto)
[7.] Give those mixes that do not contain salt. In each case also list the component with the largest relative amount and its total mass in 1 kg of mix. (07sotlan)
[8.] Give a list of the common ingredients of the Mediterranean mix and ``Flekken'' mix. (Only the type of the spice matters, its amount is irrelevant.) (08mfkozos)
[9.] Give those ingredients that can be found in exactly one of the two mixes Grill and Piquant Grill. (Again, only the type of the spice matters.) (09grilldifi)
[10.] List those spice mixes that contain the most expensive spice. For each mix, also display the price of the spice in 1 kg of mix. (10draga)
The database (i299.mdb, i299.accdb, ...) together with a short documentation (i299.txt, i299.pdf, ...) - also containing the name and version number of the database application - should be submitted.
I. 300. 175 years ago Samuel Morse revolutionized communication by introducing his telegraph system on September 4, 1837 in New York.
You should create a web page featuring the Morse telegraph. Your page should have a built-in interactive part according to the following specifications:
it should contain an input field into which one should be able to enter at most 40 characters of the English alphabet;
this text should be converted to a Morse code and animated as dots and dashes on a strip of tape, or played as beeps of appropriate length.
The web page contained in a compressed folder (i300.zip) should be submitted, including the HTML documents (with index.html as a starting page), images, sound files and any other files needed for offline viewing. Texts and image sources should be credited.
Problems with sign 'S'
Deadline expired on October 10, 2012.
S. 73. A table tennis tournament is organized in Noname city. The home address of every player is known, together with the maximal distance the player is willing to walk for the sake of a match. Since the shape of the city is highly elongated, instead of the exact address we only take into account the relative position of the player's home along the long main street, given by a house number. The walking distance, too, is measured only along the main street -- in other words, everybody can reach the main street virtually immediately.
Since a match is always played at a player's place, two given players can play together if at least one of them is willing to walk to the other's place, that is, if the difference between their house numbers is not larger than the distance the more enthusiastic player is willing to walk.
Your program should determine the number of possible matches during the tournament. Two matches are considered to be distinct, if not the same two players participate in it.
Your program reads the number of players () from the first line of the standard input. Then each of the next N lines contains the two known pieces of data for every player as two integers separated by a space: the house address (), then the maximal distance () this player is willing to walk for the sake of a match.
The standard output should contain a single number: the number of possible matches.
The table shows some inputs (``Bemenet'') and the corresponding outputs (``Kimenet'').
Scoring: You can obtain 2 points for a brief and proper additional documentation clearly describing your solution. The maximal 8 points for your program can be obtained only if it can solve an arbitrary valid test case within 3 seconds of running time. Partial points can be obtained if your program can solve only the smaller test cases within the allotted time, or those test cases in which all the maximal walking distances are the same.
The source code of your program (s73.pas, s73.cpp ...) - without the .exe or any other auxiliary files generated by the compiler - should be submitted together with a short documentation (s73.txt, s73.pdf, ...) in a compressed folder s73.zip, also describing which developer environment to use for compiling.
Upload your solutions above