The hostess made an enormous rectangular (but actually not very delicous) cake. Moreover the sides of the cake were burnt and it was impossible to remove them from the baking tin.
Guest were arriving and nobody knew what to serve them. Therefore the hostess decided to try to use at least some parts of the unfortunate cake. She took a knife and made several cuts. These cuts were horizontal and vertical line segments not intersecting the burnt sides of the cake.
Then she took the baking tin, turned it over, shook out the pieces of the cake to the plate and brought the plate to her dear guests. The baking tin and remains of the cake were left in the kitchen. Thus the guests do not know how many holes are in the original cake after shaking out cut pieces.
Task: N line segments cut into the cake are given by the coordinates of their endpoints. Write a program which determines the number of holes in the cake.
Example:
``Oook!'' marveled the librarian when he found out that today the shelf contains again other books. Yesterday the shelf contained several copies of the first and the second volumes of Lindenmayer's Digest of Magical Spells. Today there were again the first and the second volumes of the same book but their number and order was surely different. After several days of careful observations of the bookshelf the librarian discovered that the changes on the shelf obey some rules. During each night each first volume turns into the group of books u and each second volume turns into the group of books v. The groups u and v are the same each night. The librarian assigned a special task to Rincewind. He wrote a sequence of the first and the second volumes on the paper and wanted Rincewind to find out whether this sequence is going to appear on the self one day (the sequence can be surrounded by other books on the shelf).
Task: Help to Rincewind and write the program which find out the answer of the libriarian's question. The program reads as an input sequnces u, v, w, x containing numbers 1 a 2. u is the group of books into which the book 1 changes each night, v is the group of books into which the book 2 changes. w is the current state of the bookshelf and x is the librarian's sequence of book. u and v can possibly be empty sequences.
Example:
Let u=12, v=212, w=21. Each night each 1
turns into 12 and each 2 turns into 212. On the second
day books on the shelf will be 21212 and on the third day 2121221212212.
In the case x=1221, the answer on the librarian's question is yes,
because this sequence can be found on the bookshelf on the third day. In
the case x=11, the answer is no, because this sequence will
never occure on the bookshelf.
The sparrow named Cin-cin is late once again. This is already the fifth anual meeting of absolvents of the high sparrow school and he had not arrived in time to any of them. He does not want to disturb the fun of his mates and therefore he wants to choose the place to sit down in advance.
Sparrows used to sit in a row on the first electric wire out of the village between the posts EV 274 and EV 277. Cin-cin prefers not to sit at the end of a row because there one has only one neighbour to talk with. It is much better to have two neighbours. On the other hand he likes to have enough space on both sides. Therefore Cin-cin wants to sit down between those two neighbouring sparrows which have the greatest distance between them. Now he is too far to see his mates. But fortunatelly there is a chattering magpie which knows about everything what happens around. She told him about each sparrow the time of his arrival and the place where he sat down.
Task: Write a program for Cin-cin which reads in the lengths A, B of wire from the village to the posts EV 274 and EV 277, number of sparrows sitting on wire N and for each sparrow the length of wire from the village to the place where he sits. Program should find two neighbouring sparrows with the greatest distance.
Note: Solutions working in linear time are welcome.
Example:
Input:
A=5, B=16
N=5
Locations of sparrows: 9,13,7,15,10
Output:
The neighbours with the greatest distance sit at locations 10 and
13.
Enormous deposits of rum II where recently discovered beneath the surface of Tiribaki Islands. Considering their problems with rum 1 engineers have built only one big rum well but the transportation of rum II from this well is not solved yet.
After several draughts of rum they projected a large rum-line net consisting of rum-pipes and regulation stations. One hectoliter of rum can flow through each rum-pipe per one minute. Each pipe connects two regulation stations, in these stations one or several pipes can meet. The total amount of rum which flows into the regulation station is equal to the total amount which flows out of it. Entire net is directly connected to the rum well in the regulation station s and rum transported by the net is consumed in the regulation station t located in the nearby city.
In the morning engineers considered soberly their project and realized that althought it would be a magnificent construction the amount of rum which could be transported by their net would me rather small.
Task: Given are the number of regulation stations N and the number of rum-pipes M followed by M pairs of numbers. Each pair represents one rum-pipe (numbers of regulation stations which it connects). The station s is number 1 and the station t is number N. Write a program which computes the amount of rum which can be transported by this rum-line net per minute.
Note: Assume the amount of rum which flows from rum well to the station s is the same as the amount which flows out of s and that all rum which flows to t can be consumed there.
Example:
Input:
N=4,M=5
Rum-pipes: (1,2), (2,3), (1,3), (3,4),
(1,4)
Output:
Rum line net can transport at most 2 hectoliters of rum per minute.
Correction of the task The Stevo's Network: Our department of history research discovered that Stevo did not eat bacon since he does not like it. He ate carrot instead.
Stevo ate all his carrot and took a look round. When he saw what his friends were doing he was shocked. The computer net was in total chaos. Stevo started to climb to the trees, disconnect and connect links and after several minutes all the computers were connected in one circle. He looked at his work with satisfaction.
And Stevo said: if you want to solve some problem you have to elect your leader! And students of the Faculty of Mathematics and Physics started to think about his words and they saw he was right.
Task: Each computer is connected with two neighbours in the circle by individual links. The links of each computer are numbered 1 (the left neighbour) and 2 (the right neigbour). Each computer in the network has its unique name (string of at most 10 letters not containing spaces - e.g. FERDO). If computers A and B are connected by a link, the computer A can send the message to the computer B; the message is stored in B's mailbox.
Write a program which all Stevo's friends run on their notebooks (while thinking about his words) and after this program terminates, each of the computers will know the name of the leader (since there can be only one leader, each computer has to find the same name, but it is not important which of the computers will become a leader). The program runs independently on each computer.
You can use following procedures for communication between computers (when using C language or other language, use procedures with similar structure; smes is the same as string, but its length is unconstrained):
Note: The computers should find their leader soon. Otherwise the students will think about Stevo's words for too long and this can have overwhelming consequences. Links are very slow and therefore try to minimize their usage.