 |
Exercises and problems in Informatics |
Please read The Rules of the Problem Solving Competition.
New exercises of sign I
I. 91. Let us experiment with the help of Euklides geometry program.
Consider a regular hexagon ABCDEF with vertex A fixed and vertex C running through a given line e, so for any position of point C=C' we have a similar regular hexagon AB'C'D'E'F'.
a) By inspecting the animation generated by Euklides or by using some other built-in capabilities of the program (e.g., simultaneously displaying frames of the animation), determine the loci of vertices of the moving hexagon. Could you provide arguments supporting your conjecture?
b) What region is swept by the circumscribed disc of the regular hexagon? (Of course, the radius of this disc also varies.)
A file (i91.txt) in TEXT format (!) is to be submitted containing your observations and arguments.
(10 points)
Remark. We called the readers' attention to the program Euklides already in the September issue of our journal. The program can be located and downloaded from the Internet.
I. 92. Elves at Santa Claus' home are packing presents. Santa Claus has no boss and every elf is (indirectly) his subordinate. Each elf knows only his or her immediate boss and immediate subordinates. Santa Claus suddenly decides that he wants to have a copy of the current issue of KöMaL packed into each present. Since Santa Claus is hard pressed for time, he is anxious to get all elves to learn about his decision as soon as possible. Elves however can only notify their immediate subordinates one by one, each in a unit of time. How much time is needed to notify all elves and in what order should elves notify their subordinates? Create a program that computes and displays the most efficient (e.g., the fastest) way of notification, if a graph describing the boss-subordinate relationship between elves and Santa Claus is given.
Your program (i92.pas) is to be submitted.
(10 points)
I. 93. The aim of this exercise is to demonstrate some of the fundamental operations of integer arithmetic among numbers having at most 50 digits. Prepare a sheet (i93.xls) such that when two integers are entered into its second and third row, respectively (with at most one digit in each cell, further aligned in a way that corresponding place values fall beneath each other), then the sum, difference and product of the two integers appear in the fourth, fifth and sixth rows, respectively. The sheet (i93.xls) is to be submitted.
(10 points)
| 1 | 5 | 6 | 7 | 9 | |||||
| 3 | 5 | 4 | 8 | ||||||
| 1 | 9 | 2 | 2 | 7 |
Send your solutions by e-mail to: i@komal.hu
New problem of sign S
S. 4. The game Sokoban is played on a rectangular grid. The goal is to drag all the boxes onto the target squares. (The number of boxes is equal to the number of target squares on the board.) In every step, our worker - called Sokoban - either moves in any of the four directions (up, down, left or right) to a neighboring free square or pushes exactly one box in front of himself. (More than one box can not be pushed onto the same square.) Some squares are marked as ``walls'' - Sokoban of course is not allowed to move onto walls or push a box onto such squares.
Write a program that finds the shortest solution to the puzzle, that is, find the shortest path of Sokoban. (If there are more than one shortest paths, then Sokoban can choose any of them.) The program should read the initial state of the board from the standard input. The first row of the input contains the height and width of the board, while the remaining rows describe the board itself using the general Sokoban notations:
| # | Wall |
| $ | Box |
| space | Floor (empty cell) |
| . | Target square |
| * | Box resting on a target square |
| @ | Sokoban |
| + | Sokoban standing on a target square |
The program should write the result to the standard output. The first row of the output should contain the length of the shortest path of Sokoban, while the second row should contain his directions of movement, encoded by the letters U (up), D (down), L (left) and R (right). If there is no solution at all, your program should display the text NO SOLUTION.
The dimensions of the board are at most 15x15 and all boundary cells will consist of walls. The number of boxes will be at most 3. The input will be correct, no check is needed. Your program should not display anything besides the result.
Example:
| Input | Output |
|---|---|
6 7 ####### #@#.### # * # # $ # # # ####### | 14 LJJBLLJFFLJJFB |
(10 points)