Mr. Zavis have tried another idea how to became rich. He have founded a snail farm. The garden is now full of crawling snails. Snails grow rapidly - Mr. Zavis have noticed that their spiral shells enlarge by one turn each month. Mr. Zavis decided provide his customers with a booklet containing pictures of snails of various ages. Since he does not own any camera, he wants to print pictures on his printer.
Task: The input consists of age of a snail (given in months) and direction of this snail (which can be left or right). Write a program which prints such snail on a printer. Snails should be similar to those shown in an example.
Note: Printer can print only one character after another printing lines from top to bottom and going from left to right in each lines. If you use Turbo Pascal, you can use unit PRINTER. When using this unit you can print using commands write(lst,...), and writeln(lst,...).
Example:
age: 1 month, direction: left
H * H**
age: 2 months, direction: right
**** * * * ** * H ******H
age: 3 months, direction: left
******** * * * **** * * * * * * ** * * * * * ****** * H * H**********
Zeofine finished to draw the last Galapagian tree late in the evening. She was very tired. She found a nice place in a sand and she fell to sleep. But she had a nightmare. Zeofine escaped to a desert from a laboratory where they forced her to traverse labyrinths. They wanted her to use each corridor of a labyrinth but she could not use any of them more than one. This night in her dream she was again in one of those labyrinths. First of all it has only one straight corridor. But before she could pass this corridor, the labyrinth had changed. Two side corridors appeared. But started in one third of the original corridor length and ended after two thirds of the original corridor. Both side corridors consisted of three straight parts, each of these parts had length one third of the original corridor. Before Zeofine decided how to traverse this labyrinth, it has changed again. New side corridors appeared at each straight part corridor of a former labyrinth. And in this way new side corridors were appearing until she woke up. Zeofine was scared and she would feel much better if she would know how to traverse labyrinth which appeared in her dream.
Task: The labyrinth of degree 0 has only one straight corridor (it can be depicted as a line segment). Labyrinth of degree n+1 can be constructed from a labyrinth of degree n. First we divide corridors of the original labyrinth into straight sections going from one crossing or turn to another. All these sections have the same length l. Then we draw additional rectangle across each such section. This rectangle has its shorter side l/3 long and parallel to original section and the longer sides is 2l/3 long and is divided into two halves by the original section. Moreover The rectangle divides the original section into the three parts of the same length. The length of the shortest section in a labyrinth will be denoted d.
Write a program which helps Zeofine to traverse a labyrinth given by its parameters n and d. The output of your program should be a series of command for Zeofine. Zeofine knows these commands: Forward a - she moves a length units forward according to her direction, Left u - she turns u degrees left, Right u - she turns u degrees right.
Example:
Tusks of an elephant consist of ivory which is very precious material. Recently genetics engineers of one African country have cultivated a special kind of an elephant whose all bones consist of ivory. Since this country is very poor, they want to sell some of the bones but they do not want to endanger their elephant.
Thus scientist have thoroughly examined the elephant and the noticed that there are some important points in its body and each bone connects two such important points. Moreover the elephant survives surgical removal of some bones if its skeleton remains connected (i.e. all important points of its body are connected by some bones maybe via other important nodes). Now they want to remove some of the bones so that the elephant survives the operation and bones which are not removed have the lowest possible value.
Task: Write a program which reads the description of the skeleton and determines which bones can be removed so that the elephant survives the operation and the sum of values of bones which remains in its skeleton is minimal. The description of the skeleton starts with a line containing the number of important points N and the number of bones M. This is followed by M lines, each of them describing one bone. Each bone is given by three numbers A, B and C, where A and B are numbers of important points which are connected by this bone and C is a value of this bone.
Example:
Input:
5 6 1 3 5 5 1 3 2 4 9 4 3 4 1 4 1 4 5 4
Output:
5 4 1 5 3 2 4 9 4 3 4 1 4 1
Jonathan was sitting in the kitchen and watching his mother preparing his breakfast. He was still very sleepy. She was cutting thin slices of cheese, vegetables and other food and then she laid these slices on the slice of bread. Jonathan took his fork and he tried to stick his sandwich on it thoughtlessly. But in vain. The fork was too short and the layer of filling was too thick and therefore only part of the filling was stuck on a fork and the sandwich itself remained on the table.
Task: Assume that the slice of bread is a rectangle of size AxB (A and B are positive integers not exceeding 100) and all slices of a filling are rectangles of thickness 1. These slices are arranged so that their sides are parallel to the sides of a slice of bread and lie within the slice of a bread. Lower left corner of a sandwich has coordinates [0,0]. The length of prongs of the fork is k. It means that the sandwich can be stuck on the fork only on those places, on which there are less then k slices of filling.
Write a program which reads the sizes of all the slices and their coordinates as well as the length of fork prongs k. Your program should determine whether there exist a place on a sandwich where it is not possible to stick the bread (i.e. where there is a point which lies inside at least k rectangles corresponding to slices of filling).
Example:
Input:
A = 7, B = 8, K = 3
Size Lower left corner ------------------------------------------ 4x4 [1,1] 2x2 [4,6] 3x1 [3,3] 2x5 [2,2]
Output:
There is a place on a sandwich where it is not possible to stick a
bread.
Witch named Kirke has bought new curtains. She was content with cobwebs of her darlings but now she wanted some change. Now she wants to hang the new curtains so that the gap between two adjacent nippers will be the same. Moreover this gap can not be longer than d.
Kirke is very good in estimating one half of some length. Therefore she fixed curtaqins by nippers at both ends. Then found a place exactly in the middle between these nippers and she placed a nipper there. Then she continues in adding nippers so that she chooses come gap between two nippers which is still longer then d and she divides it with a nipper into two halves. She repeates this operation until no gaps are longer than d. It is obvious that at the end all gaps will be the same. The problem is that Kirke is quite old and she wants to move as little as possible. Therefore she wants to add nippers in such an order that her hand will have to move along the shortest possible path.
Task: Write a progam which read the length of a curtain l and the maximum gap between two adjacent nippers d and determines the order of adding nippers so that Kirke will move along the shortest possible path. In the output describe the nippers by their distance from the left end of the curtain.
The important part of your solution is a proof that sequences written by your program are really best.
Example:
Input:
l=8, d=1
Output:
The hand of Kirke should move along the path of length 23.
The order of nippers:
0,8,4,2,1,3,6,7,5
(There are also other orders nippers with the same length)