Deadline for sending solutions of the 1st series is October 19, 1998
CSPers
The cubivers is a rather dull place. It consists of n square fields lying in a row. The cubivers is inhabited by the only animal species - the cuber and by a transsensual, unperceivable being without a shape, colour, taste or odour - the Cugod.
The cuber is cube-shaped. It arises when and where the Cugod desires. Afterwards the cuber IS, EXISTS, but nothing more - it does not make a slightest move. Then suddenly the Cugod wishes the cuber vanishing and the cuber really disappears. The Cugod wishes occasionally several cubers to arise in a line for instance from the field a to the field b. Immediately after that one cuber appeares on each of the fields a,a+1,a+2,...,b-1,b. The Cugod can analogously wish one cuber vanishing on the fields c to d. The Cugod is infallible so he has this kind of wish only if there is at least one cuber on each of these fields. And thus the columns of cubers on particular fields of the cubivers rise and fall.
From time to time the Cugod philosophically queries: "So, how many cubers are on the r-th field?" Or: "So, how many fields are inhabited by one cuber at least?" Having a long time he learnt to program and now he spends long whiles meditating how he would program that. Show that you are at least as good as the Cugod.
Task: You are given the number of fields of the cubivers n. The cubivers is void at the beginning. Your program is receiving messages describing the changes in the cubivers or querying the actual state. Your program should use a suitable representation of the state of the cubivers to react to messages and provide information being queried. Each message is one of these types:
Example:
n=6
> APPEARE 2 6
> APPEARE 4 4
> HEIGHT 5
1
> VANISH 2 4
> ONE OR MORE
3
The way how the cubivers was changing:
"Maaaaaaaaaah, maaaaaaaah," was the sound that stroke Mrs Anastasia in her house again. Her goat named approached the cottage at the end of the garden again. It was the place where Mrs Anastasia had planted most flowers. She had driven her to graze at the other end of the garden, where the number of flowers was not that big, at least eight times that day - the vanity beyond the vanity! So finally Mrs Anastasia though unwilling decided to tie her to a peg. And she started to search for the largest flowerless area in the garden so that Livia would have enough room for grazing.
Task: Mrs Anastasia would like to tie Livia by a string to a peg. She needs to find such a place to pin a peg that Livia can graze the largest area possible but the string must be of such a length that Livia cannot reach any flower nor can go out of the garden. Suppose the garden is a rectangle A x B.
Write a program which reads the dimensions of the garden A x B, the number of the flowers N, their coordinates (x1,y1) to (xN,yN) and finds the centre and the radius of the largest circle lying in the interior of the garden and containg no flowers. If there are more circles with the biggest area, output the centre and the radius of any of them.
Example:
Input:
Dimensions of garden: A = 3.0, B = 2.0
N=5
Flowers:
(0.5, 0.5), (0.5, 1.5),
(1.5, 0.5), (1.5, 1.5),
(2.5, 0.5)
Output:
Centre: (2.225, 1.225)
Radius: 0.775
The king of Burundi was observing the falling graph of his preference. It was not a reason for losing his comfort but he was a bit sad. He had the main counsellor called and asked him what to do. The counsellor counselled: "People like the change and Your Majesty has been on the throne for the whole of ten years. Your Royal Highness might offer them the change and arrange the election" The king was terrified but when the counsellor explained to him that there would be only one candidate he approved with a great excitement.
Not long after this the king was observing the schedule of pre-election meetings. There was the place and the day of each meeting on the list. When the king looked at the list closer he found out to his horror that there are too many meetings there and he cannot participate in all of them. Burundi is a big country with bad roads and transport from one place to another may take several days. The king did not hesitate and promised 50 per cent of the shares of West Burundi Iron Mills to the person who would find the route of pre-election trip with the most meetings possible.
Task: Burundi has N cities numbered 1 to N. You are given the list of Burundi roads (all are connecting exactly two cities in both directions) and for each road a time that driving from one city to the other would take. Furthermore the date and the place of each meeting is given. The king is on day 0 in the capital (the city number 1). The time the king is going to spend at the meetings is negligible and his pre-election trip does not have to finish in the capital. Write a program which reads the list of Burundi roads and the list of meetings and determines the maximum number of meetings that the king can attend.
Example:
Input:
4 cities
roads:
from 1 to 2 in 4 days
from 1 to 3 in 3 days
from 2 to 3 in 4 days
from 2 to 4 in 5 days
from 3 to 4 in 2 days
meetings:
city #1 day 3
city #2 day 4
city #3 day 9
city #1 day 12
city #4 day 17
Output:
The king can attend at most 4 meetings.
Jane is a researcher and works in the laboratory for the research of the intelligence of animal species. Anyway, she is a small white mouse which likes the cheese. After a few weeks of the patient work she managed to train her man. Whenever Jane runs up the ladder he gives her a piece of tasty cheese.
However, Jane is not hungry now. A while ago she was surrounded by several cubes with letters. She swept most of them to the corner but a few of them remained. She tried to order them to compose a palindrome, i.e. the word which reads the same forwards and backwords. She was surprised to see the man coming after a while with a piece of Emmenthal and the next heap of cubes. He put them in a row and inconspicuously withdrew. Jane got immediately what the man wanted her to do. She should insert some other cubes in the row to constitute the palindrome. She instantly started to conceive what is the least number of cubes that have to be inserted in the row (the cubes are heavy and Jane does not want to bring too much effort).
Task: Write a program which reads an input word w = a[1]a[2]...a[n] and determines the least number of letters which have to be added to obtain the palindrome. New leterrs can be inserted between two arbitrary neighbouring letters, at the beginning and at the end. Write out one of the obtained palindromes.
Example:
Input:
abab
oitsoppoitin
Output:
babab (number of letters added: 1)
noitisopposition (number of letters added: 4)
You must have noticed that the good end of many fairy-tales is due to various good fairies and similar elements who advise the hero when facing helpless situation. Even professor Indigo has noticed that and he has found the way how to use this unique ability of theirs. Indigo realized that though computers are able to solve many problems, they might be helpless from time to time too. Even the computer would sometimes appreciate some advice. Professor decided to construct the cunning computer (CC) which would make use of the collaboration with a good fairy. Amalka the fairy agreed to cooperate and help the cunning computer with computations. Thus the computer Amalka inside came into existence.
The cunning computer can solve the problems which have yes/no answer. Professor has elaborated a compiler of Pascal (C/C++ respectively) for CC which does not support any commands to work with input/output devices (such as display, keyboard or hard-disk) so far. Data input is managed by passing parameters using key word program. In order to establish delivering parameters of composite types as well, Indigo allowed the declarations of types and constants before the key word program. For example
const MAX = 10; type point = record x,y : integer; end; program MyPrg(P : point; a : array[1..MAX] of byte);
is the header of the program which receives one variable of the type point and an array of 10 bytes. The commands fail and accept are used to terminate the program. The command accept causes the program to deliver yes answer. The command fail means something like ``I have not succeeded to answer yes'' (more exact description is to be given later)
The last new construct is the command choose which is used in the same manner as the command case but it does not contain any expression determining the branching. For example
choose 1 : Command1; 2 : begin Command2; Command3; end; end;
Whenever during the execution of the program Amalka inside encounters the command choose, Amalka the fairy determines which branch should be executed.
In C/C++ the input data is delivered as the parameters of the function main. The commands fail and accept work similarly as return but they do not have any parameters and always terminate the program. The construct choose is an analogue of the construct switch without the control expression. Amalka determines the case where to jump. (you may propose similar constructs for other programming languages).
Amalka controls the execution of program in such a way that it gives yes answer whenever possible. It means that whenever there is a sequence of branchings choose leading to the command accept for a given input, Amalka inside answers yes. If there is no such seqence Amalka inside answers no (Amalka being a genuine fairy can foresee that no sequence of branchings leads to the accept and stops the computing). Hence Amalka inside answers no if every sequence of branchings choose leads to the command fail, different possibilities of the termination or the computation according to this sequence does not terminate.
Professor Indigo has written the first program for the cunning computer. It is here:
const MAX = 100;
type tarray = array[0..MAX-1,0..MAX-1] of integer;
program FirstProgram(N : integer; p : tarray);
var x,y : integer;
begin
x:=0; y:=0;
repeat
choose
left: x:=x-1;
right: x:=x+1;
up: y:=y-1;
down: y:=y+1;
end;
if (x<0) or(x>=N) or (y<0) or (y>=N) then fail;
if p[x,y]<>0 then fail;
if (x=N-1) and (y=N-1) then accept;
until false;
end.
Nevertheless, the professor is not quite sure whether everything works as it should. In order to assure that he needs a program which does the same but does not make use of Amalka's abilities.
Task: Write a program which does exactly the same as the professor's first program (i.e. both programs give the same answers to same inputs) but does not use the construct choose and always terminates by the command accept or fail (so your program does not need Amalka the fairy).
1998, Organizers of the CSP