KöMaL Problems in Informatics, March 2008
Please read the rules of the competition.
Show/hide problems of signs:
Problems with sign 'I'
Deadline expired on April 15, 2008.
I. 181. In this exercise you will have to display a stitchwork. On the first inside cover, half of the stitch pattern is given, which can be downloaded from here (beka.txt) (tabulator-separated file).
You should read the file beka.txt with a spreadsheet application. The first piece of data should be put into cell A1 of the sheet ``Beka''. (The data may also contain empty cells meaning no stitches.)
Letters in the pattern should be interpreted as follows:
Make some adjustments to the figure containing characters similar to the given image: the width of column A:AX and the height of line 1:50 should be set such that cells become visible squares on the screen .Data describing half of the image is contained in the range A1:Y50. The other half of the frog should be generated symmetrically using functions that can be copied. You can use conditional formatting to display colours.
Beginning with cell AY:51, a statistic should be generated describing colours used in the pattern. Try to use expressions that give correct answers even when copied.
The sheet ``Derek_beka'' should contain a rotated version of the frog (90 degrees in any direction) using appropriate functions, while sheet ``Nagy_beka'' should display an enlarged version (with ratio 2) of the pattern on the original ``Beka'' sheet.
Your sheet (181.xls, 181.ods, ...) together with a short documentation (181.txt, 181.pdf, ...) should be submitted containing a description of your solution and the name and version number of the application.
I. 182. Prepare your program to simulate the motion of cars in a roundabout using a character display. The roundabout connects two perpendicular roads. Roads are numbered from 1 to 4 anticlockwise. If a car plans to travel further on road nafter it has left the roundabout, it is marked with that number n. (A car can also turn back: the incoming road segment can be the same as the outgoing one after one full round.)
In each simulation step a new car appears with probability pi (i4) at the beginning of each lane on the border of the grid (provided that the first square of the ith road is free). These probabilities are real numbers between 0 and 1, and are given as the first four command line arguments to your program. Cars move with constant speed until the next square in front of them is free. If they catch a slower car, the faster one temporarily adjusts its speed to the slower one. Speeds are expressed by integers between 1 and 5. Value 1 means that the car moves forward in each step (if possible), while 5 means it tries to proceed forward only in every fifth step, otherwise it stays at rest. Cars waiting to enter the roundabout should give way to those already in there. Outgoing cars disappear on the border of the grid (see the figure).
When SPACE is pressed, the simulation should stop. Keys from 1 to 9 control the speed of your simulation.
The source code of your program (i182.pas, i182.cpp, ...) and a short documentation (i182.txt, i182.pdf, ...) should be submitted containing a description of your solution and specifying the developer environment to compile your code.
I. 183. Once upon a time, the government of a not-so-distant country decided to cut back on hospital supply expenses. Worn bed-linen are darned using a high-end hole detector. After the resolution is set appropriately, this device determines whether a given cell of the sheet is punctured. (Edges are strong enough not to contain any holes.)
The value of a given cell is V if the fabric is intact, and L, if there is a hole there. Each hole should be covered by a rectangle of new material (with sides parallel to the edges of the sheet). A group of L's belong to the same hole, if each L in the group has at least one edge in common with another L in the same group. A letter L belongs to a different hole if it is not adjacent at all, or if it only touches the corner of an L from the other hole. Rectangles can overlap each other. (The figure ``Példa két lyukas területre'' shows a sheet with two holes.)
Prepare your program which gives the number of patches to be sewn on the sheet. The name of the input file describing the sheet is the first command line argument of your program. The standard output should be used to list the number of patches in order by specifying the top left and bottom right corners of each rectangle. (First the row, then the column coordinate should be specified for each corner, relative to the top left corner of the sheet.)
The first and second lines of the input file contain two integers N and M (3N200, 3M200), giving the total number of rows and columns on the sheet. The following N lines contain M characters, either a V or an L.
The ``Példa (berajzolt foltokkal)'' part of the example is a sample input, Kimenet is the output. ``Folt'' means patch.
The source code of your program (i183.pas, i183.cpp, ...) and a short documentation (i183.txt, i183.pdf, ...) should be submitted containing a description of your solution and specifying the developer environment to compile your code.
Problems with sign 'S'
Deadline expired on April 15, 2008.
S. 34. Once upon a time, a king of a distant country decided to wed his daughter. He commanded his architect to build a labyrinth full of dragons. ``A knight is allowed to engage my daughter only if he enters the labyrinth, then leaves at any other exit,'' said the king. Moreover, the king wants to be sure that if a knight gets through the labyrinth alive (using any exit), he cuts off at least a given number of dragon heads.
Your program should verify whether a given labyrinth has this property. The plan of the labyrinth is read from a file, and the output is also written in a file. The names of these files are given as the first and second command line arguments to your program.
The first line of the input contains the width W and height H of the plan of the maze (separated by spaces, with 3W,H100), further the minimal number of dragon heads F to cut off. Each of the following H lines then contain W characters, which can be
a space, if the given square is part of a corridor, and all four neighbouring squares can be reached
J, B, F and L, if the given square is a corridor with a gate, so a neighbouring square to the J (=east), B (=west), F (=north) or L (=south) direction can not be reached
*, if the given square is a wall
a digit N (from 1 to 9), if the given square is a corridor-square with an N-headed dragon lurking on it, and that dragon should be eliminated.
Entrances of the labyrinth are the corridor-squares on the border of the labyrinth. They contain no dragons and have at least one adjacent wall-square.
The only line of the output should contain three numbers (separated by a space). If the plan fulfills the king's requirements, all numbers should be zero. Otherwise the three numbers describe a possible path from entrance A to B during which only K (K<F) dragon heads are necessary to be cut off. Entrances are numbered from the top left corner clockwise, beginning with 1. If there are multiple solutions, the minimal K, then the minimal A and B should be computed.
The source code of your program (s34.pas, s34.cpp, ...) and a short documentation (s34.txt, s34.pdf, ...) should be submitted containing a description of your solution and specifying the developer environment to compile your code.
In the example, ``Példa be'' is a sample input, while ``Példa ki'' is the corresponding output.
Upload your solutions above