3rd Series Problem Set of the CSP

Here you have a problem set of the 3rd series of the CSP. Send your solutions before deadline March 27th 1995 to our address ksp@fmph.uniba.sk

                  Good ideas and few bugs!
                          CSPers

Brutus, Frutus and Partitions
Santo's Little Cards
Tiribaki Airlines
Blue Helmets in Dinburu
The Window System

1. Brutus, Frutus and partitions

"6+3+1!", shouted Brutus like mad. "6+2+2!", contradicted Frutus. "You are 6+2+2 yourself", Brutus answered. "Your bald head!", said Frutus. The friends went out from the inn and Brutus trashed Frutus's tooth.

What did Brutus and Frutus discussed? They quarrelled about what the tenth partition of number 10 in the Nice Order was. The partition is any decomposition of the number to the positive integer addends which are ordered in the nonincreasing order (e.g. 10=6+3+1). The order, in which partition a_1+a_2+...+a_k comes before b_1+b_2+...+b_l if and only if for some u:

     a_1=b_1, a_2=b_2, ..., a_u=b_u , a_{u+1}>b_{u+1},

we call the Nice Order.

For example the partitions of the number 6 listed in the Nice Order are: 6, 5+1, 4+2, 4+1+1, 3+3, 3+2+1, 3+1+1+1, 2+2+2, 2+2+1+1, 2+1+1+1+1, 1+1+1+1+1+1

Problem: Write a program which reads the numbers n and k and as an input and writes the kth partition of the number n in the Nice Order as an output.

Note: In this case Frutus was right.

2. Santo's little cards

Once old grand PraSanto cut 32767 little cards for the old family game. He wrote number between 1 and 32767 on every little card (on each card there was a different number). He wanted to begin to play that game but suddenly the wind began to blow and scattered all the little cards around. PraSanto quickly picked them up and when he counted them he realized that one is missing.

Since that time every Saturday evening the whole Santo's family comes to Santo's home porch and they try to find which one little card is missing (they want to make the lost card again and play the old family game). Santo does not like it and he wants to stop it (because Banto comes and drinks his bar dry every time).

Problem: The input consists of 32766 different numbers between 1 and 32767. Write a program which finds the missing number (i.e. the number between 1 and 32767 which is not in the input) as quickly as you can and using as little memory as you can.

3. The Tiribaki Airlines

Inhabitants of Tiribaki Islands decided to leave sailing on cane-boats and to travel by airplanes. They built an airport on each island. The problem is that the direct connections are limited by flying range of planes. Planes can do intermediate landing on the other airport, refuel and continue but this causes that length of flight becomes longer (length of flight between two airports is their crow-fly distance).

Problem: Write a program which reads coordinates of airports, flying range of plane and two airports s and t and outputs how plane must fly from airport s to airport t to minimalize the length of flight (the output consists of sequence of all intermediate landings).

4. Blue Helmets in Dinburu

Because demand of king Ubugulundibumbuluku to the throne was very doubtful, citizens of the city Burabujum elected their own president Ntybantuganyu and started to create territory of new Republic of Dinburu. The territory has a shape of polygon (not necessarily convex!).

The UNO decided to send to Dinburu very well trained parachute unit of Blue Helmets. When the parachutist falls down he has to quickly find out whether he is in the territory of Republic of Dinburu or not.

Problem: Write a program, which reads coordinates of polygon vertexes which are sorted counter clockwise and coordinates of places where parachutists fell down. For each such place the program write, whether it lies inside the polygon or not.

5. The Window System

The software firm SoDr has a new client who bought a computer network with collection of different terminals of different type, size and age. Programmers with great difficulties wrote a few basic routines which they can use on each terminal. This is not enough because products of SoDr are known for their good user interface.

Problem: Write a library which enables to work with windows on those terminals. Your library has to provide these functions:

Window opening: opens empty window (i.e. no frames etc.) in given rectangle on the terminal screen. New-opened window is always active. Do not forget that new-opened window can overlap parts of previously opened windows.
Activation of the window: given window is brought to the top (i.e. no part of this window will be overlapped by another window).
Output of character into active window: the given character writes at given coordinates in active window (according to the left upper corner). You can suppose that output to the terminal screen will be processed only by this function.
Active window closing: closes active window (i.e. the content of the closed window disappears from the terminal screen and parts of all windows which were overlapped by the closed window are restored).

For output to terminal you can use only these procedures and functions (declarations are in Pascal, if you use another programming language you can use analogical definitions):

procedure Write(ch:char): puts character ch into actual cursor position and moves cursor to the next column (or first column of the next row).
procedure GotoXY(x,y:byte): moves cursor into the row y and the column x.
function GetRows:byte: gets the number of terminal rows
function GetColumns:byte: gets the number of terminal columns