The 4th Series Problem Set of the CSP

here you have the 4th Series Problem Set of the CSP. We noticed the we have to write a few more instructions to you about the form of your solutions:

• We prefere you send your solutions by ordinary mail rather than E-mail. Participants from Czech Republic: please, do not send your solution by E-mail!
• If you submit your solutions by E-mail please notice that we are able to work only with plain ASCII texts sent as message (i.e. we will not accept any arj-ed or UUencoded files)
• Do not write the solutions of two different problems at one sheet of paper! Do not tie papers with different problem solutions. Tie papers of one problem solution together.

The deadline of submission of your solutions is May 15th 1995

Contents

• The Flea Dance
• The Pencil Factory
• The Big Hunt
• The N-ris
• Big Numbers

The director of Hilbert's Circus decided to add a new performance to the programme. The Flea Dance won the competition. The Flea Dance is danced simultaneously by N fleas numbered from 1 to N. In the beginning they stand on fields numbered from 1 to N. There are N arrows drawn from field to field in such a way that in each field exactly one arrow starts and exactly one ends.

In the beginning each flea sits in the field with the corresponding number (i.e. the ith flea sits in the ith fields). Every second each flea jumps from its field to another following the arrow (all fleas jump at once). The Flea Dance is over when all fleas have returned to their starting fields. The director wants the performance to last as long as possible. Therefore he needs to arrange arrows wisely.

Problem: Write a program which reads the number of fleas N and writes how to arrange arrows so that the performance will take the longest possible time. The program should also write the time which the performance will take.

Example:

Input:  N=5
Output: 1-2 2-1 3-4 4-5 5-3
        The performance will take 6 seconds.
Input:  N=8
Output: 1-2 2-3 3-1 4-5 5-6 6-7 7-8 8-4
        The performance will take 15 seconds.

The pencil factory HOK-NI-RO produces high-quality hand-made pencils of various lengths. The pencils are distributed in boxes. Each box contains N pencils sorted according to their length. Because of automation the factory bought a new sorting machine. The machine has a ruler to measure lengths of pencils and a mechanical hand which can swap two pencils. The problem is that the mechanical hand is damaged and now it can swap only pencils separated by exactly one another pencil. In the factory they need to know whether it is possible to sort a given set of pencils.

Problem: Write a program which reads the number N and N lengths of pencils and writes whether this set can be sorted by the machine or not.

Example:

Input:  N=4 2,3,1,4
Output: Pencils cannot be sorted.
Input:  N=3 3,2,1
Output: Pencils can be sorted.

Santo's family has argued with Banto's family because of Old Santovka's portrait. The families got their old guns and the big hunt began.

The situation became so complicated that the sheriff really cannot say about any citizen he sees which family he/she belongs to. He decided to send his assistants to observation points. They are sending him messages containing two names, meaning that the person with the first name tried to hit the person with second name. From these messages the sheriff wants to find out who belongs to which family. He knows that there are only two families involved in the conflict and there are no conflicts inside the families (i.e. members of one family don't shoot at each other).

Problem: Write a program which reads the number of messages N and the N messages (each message contains two names) and classifies the citizens into families. If there is not enough information for unique distribution the program writes: "INSUFFICIENT INFORMATION". If there is no way of distributing the citizens according to the data the program writes: "INCORRECT INFORMATION".

Example:

Input:  Santo,Banto  Banto,Jim  Jim,Santo
Output: INCORRECT INFORMATION
Input:  Santo,Banto  Jim,Bill
Output: INSUFFICIENT INFORMATION
Input:  Mary,Santo  Bill,Banto  John,Jim   Bill,John  Mary,Bill
Output: Santo,Jim,Bill vs John,Mary,Banto

Programmer Oh Big decided to write a modification of the well known game Tetris. The difference between this game and Tetris is that the falling pieces consist not of four, but of N small squares. For three days he has been sitting in his room and drawing on paper all possible pieces which can be made from N small squares, but he is really not sure whether he has drawn all possible pieces or not.

Problem: Write a program which reads the number N and writes all the different falling pieces made from N small squares and their number. Rotated pieces are considered to be the same.

Example:

Input:  N=4
Output: ##  #      #   ##  ##    #
        ##  ###  ###  ##    ##  ###  ####
        There are 7 different pieces.

Once the employees of the Mathematico - Mathematical Faculty of the Mathematical University ordered from the SoDr software house a program. The program has to facilitate computations involving large numbers. The numbers they want to work with are integers not longer than 257 digits (the numbers can be both positive or negative). Problem: Write a library for employees of MMF MU which will enable them to work with large integers whose decimal representation is not longer than 257 digits. Your library should contain the following procedures (you can use similar declarations to those recommended for Pascal programmers):

• GAdd(a,b,c,err) --- addition (c:=a+b)
• GSub(a,b,c,err) --- subtraction (c:=a-b)
• GMul(a,b,c,err) --- multiplication (c:=a\times b)
• GDiv(a,b,c,r,err) --- division (c:=a\mbox{\ div\ }b; r:=a\mbox{\ mod\ } b)
• GAbs(a,c) --- absolute value (c:=\mbox{abs}(a))
• GInput(a,err) --- input of a large number a
• GOutput(a) - output of a large number a

In all cases the variable err contains zero if the operation was successfully completed or an error number if there was an error during the operation (e.g. overflow).

Do not forget that it is important to write detailed descriptions of the function of these procedures and the data structures used.