KöMaL Problems in Informatics, December 2012
Please read the rules of the competition.
Show/hide problems of signs:
Problems with sign 'I'
Deadline expired on January 10, 2013.
I. 307. We investigated the paths of billiard balls in problem I. 298: we were given a square billiard table of size N×N with point-like balls initially having integer coordinates within the table. Balls are reflected in a perfectly elastic manner when colliding with each other or with the boundary.
Your program i307 should first read the parameter values, then save the path of a ball with two collisions into a file using SVG vector graphics format. The ball is started from a point with coordinates (k,l) and hits another ball located at (x,y).
The ball should have 2 collisions with the walls and it should not touch any third ball. (The reason we do not consider collisions with other balls in our model is that -- due to the perfectly elastic central collisions -- the ball hit by the original one would begin travelling in the same direction.) 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 an image of the billiard table, the balls and the path with 2 wall collisions depicted as arrows in an SVG file.
Generating an SVG figure was the topic of our problem I. 243, but you can find more information on the image structure at, e.g., ``http://svg.elte.hu/''.
You can set properties of graphical elements (e.g., color, line thickness) arbitrarily.
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 example ``Példa a bemenetre'' is a sample input, while ``Kimenet SVG ábrája'' is the SVG image of the corresponding output.
The source code of your program (i307.pas, i307.cpp, ...) together with a short documentation (i307.txt, i307.pdf, ...) should be submitted in a compressed file i307.zip, also containing a brief description of your solution and specifying the name of the developer environment to use for compiling the source code.
I. 308. The first Formula 1 Championship was organized in Hungary in 1986. In this task you are going to work with the data collected that year. You should use the UTF-8 encoded and tabulator separated text file 1986.txt downloadable from our site.
Whenever appropriate, you should use - possibly copyable - formulae.
[1.] The content of the file 1986.txt should be copied to a Places(Helyezések) sheet beginning with cell A1.
[2.] Data from the 1st row of sheet Places should be copied to a Points sheet beginning with cell B6, moreover, the content of columns A and B of sheet Places should also be copied so that data coming from the 1st row and columns A and B become adjacent in sheet Points.
The following tasks refer to the Points sheet.
[3.] In range D7:S36 you should determine the drivers' points obtained in each race. The 1st, 2nd, ..., 6th place is worth 9, 6, 4, 3, 2 and 1 point, respectively. If a driver did not score any points in a particular race, the corresponding cell should remain empty. Auxiliary computations can be performed on sheet Places beginning with cell A40.
[4.] Cell T6 should contain the text ``Total points'' (Összpontszám). Below this you should determine for each driver their total number of points scored in 1986.
[5.] Cell A6 should contain the text ``Place'' (Helyezés). Below this you should determine for each driver their place, based on their total number of points.
[6.] The content of the first line should be formatted according to the sample. By writing a driver's name into cells B2 and B3, values of cells A2:A3 and C2:T3 should be determined by a formula that can be copied flawlessly throughout the whole range.
[7.] Cells U1:W1 should be filled according to the sample (``Dobogós'' means standing on a podium, ``Pontszerző'' is who scored points, while ``Helyezetlen'' is unplaced). Then cells U2:W3 should be determined accordingly by using an appropriate formula.
[8.] You should display the points scored in each race for two selected drivers on a bar chart. A second diagram should show the ratio between the podium results, point-scoring results and the unplaced ones for both drivers. These diagrams should be placed beginning with row 5, and have the same total width as the filled columns above them.
[9.] The 2nd and 3rd rows should be colored according to the column colors of the diagram. The range A1:W3 should be formatted according to the sample.
The spreadsheet (i308.xlsx, i308.ods, ...) containing your solution and a description (i308.txt, i308.pdf, ...) giving some details on your approach and the version number of the application should be submitted in a compressed file (i308.zip).
I. 309. Nowadays one can learn the usage of several programs by simply watching some video tutorials on them on the Internet. These videos typically feature an instructor solving a given problem on their computer, and the steps together with some verbal comments are recorded. With the help of program Jing, for example, one can create such videos.
Your task is to illustrate some features of the clone tool of the Inkscape program (version 0.48 or higher) capable of creating vector graphics. The length of your video tutorial should not exceed 5 minutes. You can use an arbitrary recording program, not only Jing. Your video should be uploaded to a free video hosting site.
A document (i309.pdf) should be submitted, containing the name and version number of the application used, and a link pointing to your tutorial video.
Problems with sign 'S'
Deadline expired on January 10, 2013.
S. 76. Model railway packages can be purchased from the Random Railway Toy Factory (RRTF) containing some connectable tracks, a locomotive and some railroad cars. Different packages may contain a different number of tracks, but RRTF aims to put them into a package in such a way that if each piece is used, then one can construct a railway which can be traversed by the train completely, finally returning to its starting position. In other words, the train can go on forever - or at least until the locomotive has enough power.
However, RRTF does not include any assembling instructions in the game package, so it is not surprising that some customers and their children are unable to construct the above ideal railway. So RRTF promised that if it was impossible to create an ideal railway by using elements of one's package, one would get a second package for free. Due to the challenges of assembling the track and the tempting offer of RRTF, some customers are asking for our help. After they have provided us with a description of the railway elements of their package, they would like to be given the assembling instructions of an ideal track, or, if it is impossible, they would like to have some information why it is not realizable.
A package contains the following types of elements having tracks on their both sides: a straight element of length two, a quarter-circular arc of radius one, and a perpendicular crossing of length two in both directions with intersection in the middle.
The arced element can be used in both left and right turns. On the ideal track, both ends of both directions of the perpendicular crossing element should be joined to other elements. Elements can be joined to each other only through their connecting parts. Each package contains at least 25, but at most 35 elements, and there are at most 4 crossings.
Your program should read the only line of the standard input, specifying the number of crossings, straight elements and the number of arcs, respectively, then, if an ideal track can be assembled, the program should write an ideal path to the standard output, starting from an arbitrary point and making a complete round. Elements are encoded as follows: X denotes a crossing, E denotes a straight element, a left turn is B, while a right turn is abbreviated by J. If it is impossible to create an ideal track from the given elements, then the first line of the output should be the sentence ``No ideal track can be assembled.'', and the next line should contain a short explanation -- if we can do it.
The table contains two examples. ``Példa bemenet'' is a sample input, while ``Példa kimenet'' is the corresponding output. In the second case, the output reads as ``No ideal track can be assembled. The number of arced elements is odd, hence the sum of total rotations is not an integer multiple of 360 degrees.''
The source code (s76.pas, s76.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (s76.txt, s76.pdf, ...) - also describing which developer environment to use for compiling, further a brief description of your solution - should be submitted in a compressed file s76.zip.
Upload your solutions above