Tasks of the 1st Central-European Olympiad in Informatics

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.

Task:

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.

Let n be a positive integer. We consider an ordering <, called lexicographic ordering, defined on the subsets of {1,2,...,n}. Let S₁={x₁,...,x_i} and S₂={y₁,...,y_j} be two distinct subsets of {1,2,...,n} with x₁<x₂<...<x_i and y₁<y₂<...<y_j. Then we say that S₁<S₂ if there exists k with 0<=k<=min{i,j} such that x₁=y₁,...,x_k=y_k and either k=i or x_k+1<y_k+1.

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<=2ⁿ).

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).

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.

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

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

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