The old saga says there used to be a continent named Utlantis somewhere near the border of the Discworld. But this continent disappeared a long time ago. and many of those, who wanted to find it, never came back.
One wizard named Taratlach also decided to look for Utlantis. His way lead on the sea ground and he wanted water to make him way. Thus he needed to use some magic. He found the corresponding entry in his handbook of magic. It said one should draw a circle on a seashore, stand in the centre of the circle and say the spell. After that 666 lines appears in the sand and one should say the number of line intersections which are inside the circle. But this number should be said very quickly.
Taratlach was never good in mathematics and he realized he is not quick enough even to count the lines themselves. Now he is sitting on a seashore with a sad expression on his face.
Task: Write a program which for given numbers n (the number of lines) and r (the radius of the circle) and n lines (each determined by the coordinates of two its points) calculates the number of pairs of lines which intersect inside the circle with radius r and centre in (0,0).
Example:
Input:
r=3, n=4
line p: (-2,0), (0, 2)
line q: (-5,1), (5,1)
line r: (-1,0), (-1,-2)
line s: (4,7), (4,6)
Output:
3 pairs of lines will intersect
(p and q, p and r, q and r)
Each bride in Nalomena Trieska bakes a cake for her wedding. The best wedding in this village was when smiths' Ann was marring the Andrew, the son of magistrate. Many guests gathered for that wedding and each of them got one piece of the cake which Ann baked. The cake had a form of a convex polygon with a little blue nothing in each vertex. Ann cut the cake so that each piece of the cake was a triangle with a piece of little blue nothing in each vertex.
Everything went fine until George, the former suitor of Ann, started to say that Ann could not bake such an enormous cake because there is no such baking tin.
Task: Write a program which reads the shape of the baking tin (coordinates of vertices of the convex polygon enumerated counterclockwise), the number of pieces of the cake, for each piece the lengths of its sides. Your program should determine whether the cake baked on this baking tin could be cut into given pieces (more precisely whether it is possible to arrange the pieces of the cake on the tin so that entire tin will be covered, all the pieces will be on the tin and the little blue nothing will be in the vertices of the tin).
Example:
Input:
Coordinates of the baking tin:
(0.0;0.0), (3.0;0.0), (4.5;2.0),
(3.0;4.0), (0.0;4.0)
Pieces:
(3.0;4.0;5.0), (3.0;4.0;5.0), (2.5;2.5;4.0)
Output:
The cake could be cut into given pieces.
When Cin-cin returned from the annual meeting he was very surprised. First he thought that he got lost due to his drinking on the meeting and this was not his own home. There was a lot of luggage all around the house and also a pelikan with many empty boxes. Then he saw his little beloved son Pim-pim and he knew this was really his home. He even realized that they planned to move this day!
Some things were already packed in that luggage but most of their 2-storied is to packed to those empty boxes. But it is important not to use too many boxes because their transportation is tiresome.
Task: The input consists of numbers S - volume of one box, N - the number of objects which should be packed and N numbers, each giving the volume of one these objects. All these numbers are integers. Cin-cin knows that if he would want to find how to pack his things to the smallest possible number of boxes it may take so long that even the grandchildren of Pim-Pim will die sooner. Therefore he wants to know only how to pack his things so that the number of used boxes will not exceed twice the smalest possible number of used boxes. But he needs to know the result quickly because the pelican is waiting. Write a program for Cin-cin which finds such arrangement of objects. The output should contain the number of used boxes and for each object its volume and a number of box into which it should be packed. Objects can appear in the output in any order. Also boxes can be numbered in any order. If the sum of volumes of some objects does not exceed the volume of a box they can be packed to one box.
Note: Each solution should contain the proof of its correctness, i.e. the proof that your solution will not use more than twice the optimal number of boxes. Solutions without the proof will get 0 points.
Note: Those who find this problem to be too easy can try to solve slightly different problem: Find the efficient algorithm which finds the arrangement of boxes which uses no more then three halves of the optimal number of boxes (round fractions to the nearest greater integer). With a proof of course. When you enclose the solution of this problem you can get more points.
Tribes of Dinburu finally decided to live in peace. This decision surprised the king of Dinburu very much. But he was a wise man and thus he saw that all Dinburu men are warriors and they lost their job. In order to keep the peace it was necessary to occupy them.
The king thought it to be good to have a map of Dinburu. Each citizen would like to draw the same map and hang it on his wall. It will take some time because there are only 5 colour pencils in Dinburu. The best (and only) map maker in Dinburu was assigned the job of preparing the map. He knows that each territory of a map should be coloured with such a colour which is not used to colour any of neighbouring territories. And there are only those five colour pencils in Dinburu...
Task: Write a program for the map maker which find colouring of the Dinburu territories using at most 5 colours. Input values for your program are the number of Dinburu tribes N, for each tribe the list of neighbouring tribes and the list of tribes which are neighbours with the rest of the world. Two tribes (or one tribe and the rest of the world) are neigbours if their territories have common boundary. Territory of each tribe is connected. The output of your program is a colouring of territories. The rest of the world should have some colour too, but this colour can be used for other territories not neigbouring with the rest of the world.
Note: Assume that the input is correct, it means it really describes some map drawn on the paper.
Example:
Input:
The number of tribes N = 6
Neigbours of the tribe 1: 2, 3, 4 and rest of the world
Neigbours of the tribe 2: 1, 4, 6 and rest of the world
Neigbours of the tribe 3: 1, 4, 5, 6 and rest of the world
Neigbours of the tribe 4: 1, 2, 3 and 6
Neigbours of the tribe 5: 3, 6, 7 and rest of the world
Neigbours of the tribe 6: 2, 3, 4, 5 and rest of the world
Neigbours of the rest of the world: 1, 2, 3, 5 and 6
Output:
Colouring of territories:
Tribe 1: green
Tribe 2: red
Tribe 3: red
Tribe 4: yellow
Tribe 5: green
Tribe 6: white
Rest of the world: yellow
Friends elected their leader and started to write Efficient Network Application (ENA). Stevo did not enjoy to sit on the tree with his laptop very much and he wanted to persuade his friends to continue in their hiking trip. But they were engrossed in developing their ENA and they were lazy to climb to another hill. Therefore Stevo decided to go on his own. He packed his laptop together with two cables connecting it to its neigbours in a circle and he strode away.
Meanwhile his friends completed their ENA and executed it. Unfortunately there was some error in their application and it had catastrophic effects - each computer lost all the information about the net, the name of their leader and even its own name. None of algorithms which friends wrote can be used now and they are very unhappy.
Task: All the computers are connected into one row, each computer is connected with two his neighbours in a row by direct links (except two computers at the ends which are connected only to one neighbour). Each computer is connected with two neighbours in the circle by individual links. The links of each computer are numbered 1 and 2 (or only 1). 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.
Computers have no unique identifications. Your task is to number them with numbers 1 to p where p is the number of computers in the network. No two computers can have the same number.
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 complete the task soon. Otherwise the students can get depressed, take entire network and run to find Stevo (they are too slow to catch him and they can get lost in the forest). Links are very slow and therefore try to minimize their usage.
Note 2: The number p is not known when the program starts its execution. However you may assume that this number is odd.
Note 3: Do not use the random number generator.