13th Year of the CSP; 1st Series Problem Set

The deadline for submission of your solutions is the November 6th.

About the Tiribaki Gossips
About the SoDr
About the Little Lazy Mole II.
About the Cylinderman II.
Frutus, Brutus and Furious Expressions

1. About the Tiribaki Gossips

Tiribaki women like to gossip. The problem is, that each time one woman wants to talk to another, she must sail to the island, where the another woman lives.

Unfortunately, there is not a boat route between each pair of islands so the women craving for new interesting gossips often have to change boats several times. Moreover some ferrymen are very lazy. Their boats are so slow that women rather take other (not direct) path. Tiribaki women would like to have a table, which tells for each pair of island, how much time the shortest path takes.

Task: Write a program, which inputs the number of islands N and the list of boat routes (each route is determined by two island numbers 1...N and the time of the ferry) and outputs the table, which contains time of the shortest path for each pair of islands. Assume, that time necessary to wait for a boat is neglectable.

Example:

N=3
Routes: (1,2,10) (1,3,34) (2,3,100)

Output:
 0  10  34
10   0  44
34  44   0

2. About the SoDr

In the SoDr software house they have many problems with the new customer again. He bought a computer which could use only one character variable.

Customer wants to place the computer to the frontier. Each time somebody cross the border from the first side to the second one, the computer gets character A as an input. When somebody cross the frontier from the second side to the first one, the computer gets character B. If computer got the same number of characters A and B during the day, everything is O.K. --- everybody is at home. Otherwise it is necessary to alarm.

Task: The input is the sequence of characters A and B terminated by space. Write the program, which determines, whether the number of As and Bs in the sequence is the same or not. Do not forget that your program can use only one character variable and its content can be changed only by reading from the input. You cannot use any other variables.

About the Little Lazy Mole II.

Little lazy mole II. slept in his den till the evening. His mother became annoyed with him. ``What is my lazy son growing up into?'', she told and she went to awake him. ``Wake up, mole II.'' she said sharply, ``if you don't catch the beetles in all our dens today, You'll get licking.'' What could the poor little lazy mole II. do? He did not want but he had to work.

The mole family has built N dens. Each pair of dens is connected by a tunnel. Every day mother mole and father mole creep through all their dens and they catch beetles. Because the little lazy mole II. was quite intelligent he thought a bit about it at first: ``It is the best to pass each den exactly once and to use such tunnels, that the sum of their lengths is the smallest possible.'' Of course the little lazy mole II. wants to finish his tour in his own den to have a sleep there till the following evening.

Task: Write a program, which inputs the number of dens N and lengths for all tunnels which dens are connected by and outputs the length of the little lazy mole's tour.

4. About the Cylinderman II.

Cylinderman is a man whose shape is similar to the cylinder with certain height and radius. Such people are often employed in the French wine-vaults (the more wine the employee has consumed the bigger is his radius). French wine-vaults are large rectangular underground halls supported by thin pillars. Two of a hall walls are parallel to the meridians. It often happens that some cylinderman gets stuck among the pillars and a wine-vault becomes unusable (a stuck cylinderman causes worse wine quality). Therefore each cylinderman has to consider carefully which wine-vault he can go through.

Task: Write a program which inputs size of the wine-vault (M,N), the number of pillars P, radius of the cylinderman R and coordinates of all pillars ([0.00,0.00] is the northwestern corner of the vault, [M,N] is the southeastern corner). The program outputs whether given cylinderman can go through the wine-vault from its western wall to the eastern one.

Frutus, Brutus and Furious Expressions

``I can write one!'' Brutus shouted in a cosy pub one evening. ``You can't!'' Frutus disagreed. ``Of course I can!!'' Brutus contradicted. ``Even if you derived yourself!!!'' Frutus answered.

This time they quarrelled who could write more furious expression. Finally they decided to bet. Each of them wrote his expression on the napkin and afterwards they began to quarrel which of the two expressions is more furious. In order to decide they need to know whether the expressions are not by chance identical (in this case they would probably trash each other's teeth).

Task: Write a program, which inputs two expressions consisting of one-letter variables, integer constants, signs +,-,* and brackets ( and ). The program has to output whether these expressions are equivalent or not. Two expressions are equivalent if they have the same value for each combination of values of variables.

You can assume that the given expressions are correct.