1st Series Problem Set

Zoro's Marks
Zeofine Recollects
From the Capital street
The Evil of Volleyball Championship
Help!

Dear participants,

welcome in a new year of the CSP. Deadline for submitting solutions of this serires is November 17, 1997.

We wish you many good ideas.

CSPers

1. Zoro's Marks

Zoro the Avenger presented himself in a characteristic manner. We should say, he is very particular about his image. According to the letter Z, which was sketched by three fast strokes of the sword on the wall (or on other (sur)faces), you could see what a creature he was. After great effort, the historical institute succeded in collecting a huge amount of the photographs of the buildings, where Zoro was expected to lark. The number of photographs was so high, that looking through them would take a very long time. Please, help the employees of this historical institute and write a program, which will find out how many marks Z are on one photograph.

Task: A photograph is a binary rectangular array (MxN) (consisting of zeros and ones), one Z is made of two horizontal lines and one diagonal line, and the 45 degrees angle is between them. Each line has the length of at least 3, no maximum. The diagonal line has to cross both horizontal lines. Assume no Z neighbours with another `1' in the array. Write a program counting the number of Z s in the array.

Example:
Input:

 000000000001000000010
 111111111111100000100
 000000000100011111110
 111001001001000010000
 010000010001000100000
 000111111100011111000

Output:
There are two marks Z on the wall.

2. Zeofine Recollects

It wasn't easy for the turtle Zeofine. Her sister Joffy became very famous for her math knowledge. But Zeofine was kidnapped as a child from her native Galapagas by cruel scientists to examine her abnormal abilities. As the painful years passed, she finally escaped from the laboratory in Cairo. She ran, ran and ran (as fast as the turtles can) and she didn't know how she got to a desert, where a sand-storm caught her.

When the storm ended, she looked around and saw an empty plain. After three steps she noticed the tracks she left in the sand. So she started drawing pictures of trees, to recollect the enormous trees of Galapagas, her home.

The Galapagian trees are leafless, symetrical by the axis of the trunk. Each type of the tree has a specific length of the trunk d and the angle between the branches u. The older a tree is, the more bushy it is. One-year-old tree is in fact only its trunk. A n-year-old tree (n>1) has two branches growing from the end of its trunk. First on the left side making an angle u/2 and the second on the right side in the same angle. Each branch may continue bushing, and they look the same as the trees of the age n-1, with half length of the trunk, but with the same angle of the branches.

Task: Write a program to tell Zeofine how to draw a Galapagian tree. Your program will read positive integer numbers n, u, d and will write a sequence of the commands for the turtle Zeofine. She understands these commands: Forward a - move in your direction to the distance a, Left u - turn u degrees left, Right - turn u degrees right. The turtle may cross the same line more than once.

Remark: For debugging your program you can use for example the unit Graph3 in Turbo Pascal and its functions GraphMode, Forwd, TurnLeft and TurnRight.

3. From the Capital street

Very strange people live in the Capital street. Everybody is particular about what his neighbours say about him. For example, when a man turns on the light too early in the evening, the envy of his neighbourhood would gossip: "Watch out, he is unable to save the electric power at all!" You will certainly agree that it isn't very pleasant. And you never know when you can turn the light on without the feel of anxiety. Thus all inhabitants of the house watch inconspiciously the windows of their nearest neighbours (the window left, right, up and down) whether they turned the light on already. If they did, we can too. Their luck is that each evening somebody's nerves break and in spite of the gossiping tomorrow, he turns the light on. Then it continues until all the windows, where someone is at home, are lit. (You can assume that if one window is lit in the beginning, at the end only the windows where noone is at home, remain dark).

Task: The input is the number of floors and the number of windows on each floor of the house in the Capital street. Next there is the number of windows where nobody is at home and the sequence of these windows. Each window is determined by the pair A,B, where A is the floor and B is the position of the window from the left. At the end there is the window, whose owner's nerves broke. Simulate on the screen one possible way of lighting all the windows.

4. The Evil of Volleyball Championship

In Nalomena Trieska there is an annual Volleyball Championship on the behalf of the celebration of the village foundation. Because of this great occasion every inhabitant likes to participate in the game. That is why they used to choose the best players, form the teams and start the championship. Some years before people began to protest against the chosen players - that they are not the best and why the other people could not also take part in the play.

After all the mayor of Nalomena Trieska figured out the solution to the problem. On the championship day he ordered to all people who would like to participate in the play to stand in a meadow. Then they randomly chose the position of the play area. All the people who stayed in the chosen area were players and the others created an audience. All inhabitants liked this solution and this method of choosing players is used until today. Nalomena Trieska is now again full of peace and harmony.

Task: As the input you are given coordinates of the play area (a rectangle) - the net is parallel to the shorter side of rectangle a divides it into two equal rectangles. Further you are given the number of people standing in the meadow and their coordinates. Determine which of people are players of the first team, of the second team, and which are the audience.

Note: The man standing on the border line of play area is also a player. When somebody stands on the place where will be the net, his team will be chosen randomly.

Example:
Input:
Play area: (0,2), (1,4), (5,2), (4,0)
Number of people: 4
Coordinates of people: (1.2,3), (4,4), (2,3), (3,2)

Output:
Players of the first team: (1.2,3), (2,3)
Players of the second team: (3,2)
Audience: (4,4)

5. Help!

THE KING IS MAD stop HE WANTS TO SAVE MONEY stop OLD MONEY IS DESTROYED stop NEW COINS ARE VALID stop ONLY TWO TYPES OF THEM stop WE WANT TO CONVINCE HIM THAT IT IS CRAZY stop THAT SOME VALUES CANNOT BE PAID stop HE BANNED GIVING MONEY BACK stop HELP US stop QUICKLY stop

Task: Write a program, which given two integers p, q (the two values of new coins) writes the GREATEST integer, which it is not possible to pay with only these two kinds of coins and without returning coins back to the payer. If there is no such integer, program should write a short message.

Example:

Input:        Output:
p=3,q=5       7
p=1,q=10      every value can be paid
p=6,q=8       there are infinitely many values which cannot be paid