The 2nd Series Problem Set

Dear friends,

the deadline for the 2nd series of the CSP is the 8th january 1996. Do not forget to visit our home page - its address is http://www.uniba.sk/www/csp.html. So

happy New Year with the CSP

Children from Tiribaki Islands like to play at being kings and queens --- it is no wonder since there are so many islands in Tiribaki Islands that each inhabitant can rule over one.

Once the children somehow came to possession of a map of the Tiribaki Islands. Each island was represented by a dot. The children started to play a game in which everybody has chosen a rectangular kingdom he or she would like to rule over. They do not care of kingdoms' area, the number of islands in a kingdom is important. Child, whose kingdom contains the greatest number of island, becomes the Mightiest-Direst-Strongest King.

Task: Input consist of the coordinates of the islands in the map (real numbers) and specification of rectangular kingdoms. Each kingdom is given by the coordinates of its upper left and lower right corners (integers between 1 and 100). Write a program which reads the input and writes for each kingdom the number of islands located in this kingdom.

Going home from a dentist, Brutus and Frutus visited a library. They took a book named ``The CSP Digest'' and they started to glance through it. When they finally chose the most interesting problem and wanted to read its solution, they found out this particular page was missing.

Task: Input consists of a number N and N integers in range 1...N^2. Sort these numbers.

Note: O(n log n) is not the best solution.

Banto plans to visit his grandmother Prabantovka which lives far away in a village named Nalomena Trieska. Therefore he needs to know a schedule of stagecoach routes running through Nalomena Trieska. Prabantovka does not know this schedule but she gets very excited each time some stagecoach passes her house because stagecoaches are very noisy. Every evening Prabantovka writes to her diary about all the exciting events of the day (including passing stagecoaches). Banto wants to know at least the number of the stagecoach routes running through Nalomena Trieska. He has asked his grandmother to send him the extract from her diary. Now he is gazing at her letter and he does not know what to do.

Task: Write a program which reads the extract of Prabantovka's diary and writes the fewest number of stagecoach routes that must run through Nalomena Trieska to satisfy the input data.

The extract of the diary contains beginning of the described period, the number of stagecoaches that had passed Prabantovka's house during the described period and for each stagecoach the day when it passed the house. Instead of date Prabantovka uses the number of days since her birth. The described period is 60 days long. The stagecoaches are listed chronologically.

Stagecoaches of each route arrive in regular intervals during entire described period. Each route passes Prabantovka's house at least twice during the described period. Assume there are fewer than 18 routes and that the number of stagecoaches that had passed the house is smaller than 300.

Example:

Input:

25500 17
25500 25503 25505 25513 25513 25515 25521 25526 25527 25529
25537 25539 25539 25545 25551 25552 25553

In 1101 the Viking traveller Uwe Pisgarson sailed to the South America shore. Immediately after he left his boat he was taken prisoner by natives who wanted to eat him. After much pleading Uwe convinced them to give him one more chance. The chief took him to the big room in which a big heavy stone disc hung upon the wall. It had many wooden sticks fastened all around so that it looked like the helm of a ship. The disc could be rotated in both directions. The bottom stick was red. There were little golden discs fastened to some of the sticks, some little golden discs lay on the floor. ``Look!'' said the chief to Uwe and pointed to the mosaic on the opposite wall. It showed the disc similar to the one inside the room, the red stick pointed downwards again. However, the little golden discs were arranged differently. ``If the little golden discs are arranged the same way on both walls by sunrise you will be free. Otherwise.''

Pisgarson looked at the disc carefully. He noticed that he could rotate the disc one stick in both directions or fasten or remove the little golden disc on the bottom stick (he could not reach the others).

After he stayed alone he started to work. He began to rotate the disc quickly, fasten and remove little golden discs. The disc was too heavy and he got tired quickly. Before sunrise he fainted and did not solve the problem.

Task: Write a program to save the poor Uwe Pisgarson from cruel death. Your program inputs the number N of sticks, then the configuration of the disc represented by a sequence of 0 and 1 (the sticks without the little golden discs are represented by 0) clockwise starting with the red stick and the mosaic representation similarly.

The output would be a sequence of characters L,P,V (rotate clockwise, rotate counterclockwise and fasten/remove the golden disc on the bottom stick) which says to Uwe how to solve the problem without dying from exhaustion (i.e. the length of the sequence has to be minimal).

Note: There are enough golden discs on the floor.

Life is very hard for politicians. All day they have to sit in the parliament, on meetings of many comitees, often there are some press conferences and some silly reporters want to interview them. But it is not the worst. The worst is that each politician often has to write speeches.

The most important is that the speech have the correct length. The length of the speech means number of its lines. All lines (except the last one) contains the 60 characters. The second most important is to have the speech different each time --- if the politician uses the same speech it is possible that somebody will notice its contents (but no sooner than in the next election period).

Task: Write a program which inputs the required number of lines and outputs as effective a speech as possible with the correct length. In your speech you may use the following symbols: < DP> --- dramatic pause, :-} --- engaging smile, 8-( --- righteous anger, < NSVPS> --- cries of enthusiastic agreement from the parliament.

Note: Enclose the outputs at least for 3, 10 and 50 lines in two copies.