## Cluj - Romania, May 27-31, 1994

 Day 2 - Problem A Day 2 - Problem B Day 2 - Problem C Final results

Day 1 - Problem A

Normalised Squares
For the purposes of computer graphics a part of the screen is always coded by a positive integer consisting only of digits 1,2,3,4. See the pictures:
1 2
4 3 Normalised square * is coded by 133, normalised square + is coded by 343. There is no limit on the scale of the normalised squares. If you want to shift square * to the place +, you may shift it for example 4 times down and then 2 times to the right.

Write a program into the file SQUARE.PAS which does repeatedly the following:

a) Reads a code of a normalised square from one line of the input file SQUARE.DAT as a positive integer, consisting only of digits 1,2,3,4 and a sequence of shifts L (left), R (right), U (up), D (down) as a sequence of letters L,R,U,D from the next line of the input file SQUARE.DAT ;

b) Writes the final position of the normalised square into the output file SQUARE.RES or writes message

OUT OF THE BORDER

c) Writes an empty line into the output file SQUARE.RES, until an empty line is read.

In each data set, the number of digits in the code is less or equal to 35.

The time limit is at most 1 minute for each data set.

 Example: If the file SQUARE.DAT contains 133 DDDDRR 1 DD the output file SQUARE.RES should contain 343

Day 1 - Problem B

Subsets

Let n be a positive integer. We consider an ordering <, called lexicographic ordering, defined on the subsets of {1,2,...,n}. Let S1={x1,...,xi} and S2={y1,...,yj} be two distinct subsets of {1,2,...,n} with x1<x2<...<xi and y1<y2<...<yj. Then we say that S1<S2 if there exists k with 0<=k<=min{i,j} such that x1=y1,...,xk=yk and either k=i or xk+1<yk+1.

 For example, the subsets of {1,2,3} listed in lexicographic order are: ``` {> 1 {1} 2 {1,2} 3 {1,2,3} 4 {1,3} 5 {2} 6 {2,3} 7 {3} 8 ```

The lexicographic ordering associates to each subset a natural number, as shown in the above example.

Your program should read lines from an ASCII file called P6.TXT . Each line has one of the following forms:

1 n k

2 n k1 k2 . . . ki

If the line has the first form, you have to print on the display the subset of {1,2,...,n} whose associated number is k (supposing that k<=2n).

If the line is of the second form, you have to print the number associated with the subset {k1,...,ki} of {1,...,n} (supposing that 1k1<k2< ...<ki<n).

Day 1 - Problem C

Objects

We construct objects according to the following rules:

1. The initial object is a square with the side equal to 1;

2. A new object is obtained concatenating two objects on the side which has the same length.

3. Each time a new object is constructed, it is supposed that an infinite instances of this object are available.

Requirements:

1) A positive integer n is introduced from the keyboard. Display the number of objects having the area at most n, which can be constructed if only two objects of the same dimensions will be concatenated. Two objects with the same dimensions are considered identical. For example, a valid output for n=20 is:

`     (1,1) (2,1) (4,2) (8,2) (16,3)`

where in each pair the first number represents the area of an object and the second one represents the number of distinct objects having this area

2) The same requirements must be satisfied when we are allowed to concatenate objects of different dimensions, according to the rules 1 - 3. For example, a valid output for n=10 is:

`     (1,1) (2,1) (3,1) (4,2) (5,1) (6,2) (7,1) (8,2) (9,2) (10,2)`

the pairs having the same meaning as in requirement 1).

The input is a single line introduced from the keyboard, containing a pair:

`     i n`

where i is a member of {1,2}, meaning the number of the requirement and n is the above specified integer number.

The output is a text file containing pairs of elements, as shown above.

Day 2 - Problem A

Black or white

Write a program which reads three positive integers n, p, q. Decide whether or not there exists a sequence of n integers such that the sum of any p consecutive elements is positive and the sum of any q consecutive ones is negative. If the answer is YES , your program has to produce such a sequence.

The values of n, p, q are read from the keyboard; the output consists of NO or YES followed by a sequence of n integers written on display.

Examples:
 ``` n=4 p=2 q=3 ``` The output is `NO` ``` n=6 p=5 q=3 ``` The output is ```YES -3 5 -3 -3 5 -3 ```

Day 2 - Problem B

Odd and even

Let us consider a country with N towns. A system of roads formed from direct connections between towns is given; all these direct connections are considered to have the length equal to 1. This system is called even-odd if there are two towns linked by a road of even length, as well as by a road of odd length.

a) Find out if the system of roads is even-odd or not.

b) If the answer for a) is negative, find one of the subsets X of towns which has a maximal number of elements and satisfies the following condition: for any two towns in X, if there is a path linking them, then its length is even.

The name of the input file is introduced from the keyboard. Its first line contains the value of N; the following lines contain pairs I,J with the meaning that the towns I and J are directly linked.

The value of N is at most 300.

Display the output on the screen in an intelligible form.

Examples:
 If the input file contains ```5 1 2 2 3 3 4 4 5 5 1 ``` If the input file contains: ```3 1 2 ``` a valid output is `YES` then a valid output is: ```NO X has 2 elements X: 2 3 ```

Day 2 - Problem C

Expressions

An expression contains additions and multiplications. The time needed to evaluate an addition (+) is p and the time needed for a multiplication (*) is q. The time needed to evaluate the expression AoB is equal to the time needed to evaluate the operation o plus the maximum of the times needed to evaluate the subexpressions A, and B respectively.

The operands are variables consisting of a single character, whose evaluation time is considered as being equal to 0.

Write a program which reads data from an input file that contains the values of p and q and expressions, each expression on a separate line. The parentheses are used compulsory to indicate the order of operations. For each expression one asks:

a) To find and print the time needed to evaluate that expression;

b) To find and print an equivalent arithmetic expression with a minimum evaluation time, as well as this minimum evaluation time on next line.

The equivalent transformations permitted are:

```x+y=y+x; x*y=y*x; (commutativity)

x+(y+z)=(x+y)+z; x*(y*z)=(x*y)*z (associativity).```

The results must be printed in the output file that contains an empty line between two expressions.

For example,

 if the input file contains: ```1 1 ((a+(b+(c+d)))*e)*f ((((a*b)*c)*d)+e)+(f*g) ``` then the output file must be: ```5 ((a+b)+(c+d))*(e*f) 3 5 (((a*b)*(c*d))+e)+(f*g) 4 ```

Final Results

NameCountry Final points
Alexandru Salcianu Romania580
Jiri Hajek Czech Republic522
Marx Dániel Hungary 502
Michal WalaPoland490
Krysztof SobosiakPoland478
Virgil Palancuic Romania 466
Blahut György GáborHungary450
Marek Stocki Poland430
Filip Dugandzich Yugoslavia428
Jakub PawlewiczPoland422
Kovács GáborHungary409
Iulio VasilescuRomania 393
Igor Irich Yugoslavia382
Milosh DjermanovichYugoslavia380
Renato Zeleznjak Croatia 374
David StanovskyCzech Republic372
Jan Kratochvil Czech Republic342