Problem A. Axis of choice ≡

Statement

A rectangular area with sides parallel to coordinate axises is represented by coordinates of two opposite corners (x₁, y₁) and (x₂, y₂).

Your program must find the coordinate axis which is closest to the given rectangular area.

Input file format

Input file contains four integers x₁ y₁ x₂ y₂ — coordinates of area corners.

Output file format

Output file must contain a single string:

• X if a distance from area to X axis is less than to Y axis;
• Y if a distance from area to X axis is greater than to Y axis;
• XY if distances from area to X and Y axises are equal.

Constraints

−10⁹ ≤ x₁, y₁, x₂, y₂ ≤ 10⁹

Sample tests

30 40 10 20

Y

-5 20 -4 -20

X

1 1 1 1

XY

Problem B. Boulders ≡

Statement

A pile of boulders is represented by a rectangular field of H rows with W columns each. Each element is either '.' (ASCII 46) representing empty space, 'o' representing a small boulder, or 'O' representing a large boulder.

A boulder is considered stable if at least one of the following is true:

• it is located at the last row;
• it is located directly above a large boulder;
• there are boulders of any kind both to the right and to the left of it.

Your program must remove minimal possible number of boulders from the pile so that the pile becomes stable.

Input file format

First line of input contains integers W H. Following H lines contain W characters each — pile representation.

Output file format

Output must contain H lines of W characters each — stable pile representation.

If there is more than one optimal solution, output any of them.

Constraints

1 ≤ W, H ≤ 1000

Sample tests

1 2
O
o

.
o

6 5
....oO
...ooO
..oooO
.ooooO
oooooO

.....O
.....O
.....O
.....O
oooooO

3 3
O.o
.O.
o.O

...
...
o.O

Problem C. Correctness of controller ≡

Statement

Young programmer Vasya is learning hardware design. He created his first graphics controller, which is only able to draw rectangles. Unfortunately, in some cases controller seems to output incorrect images. To help Vasya debug his controller, write a program which checks if a given image is possibly a valid output, or is definitely incorrect.

Consider the graphic scene consisting of colored rectangles with sides parallel to coordinate axes. Each rectangle has a unique color.

A scene is rendered into a bitmap by drawing rectangles one by one. Each rectangle overwrites parts of the scene drawn before it. So in the final bitmap some rectangles may be fully or partially hidden by rectangles rendered later.

Your program must, given the final bitmap state, determine whether there exists a scene which can, after correct rendering, result in this bitmap state.

Input file format

Input file contains the bitmap, represented by a rectangular matrix of pixels, one row per line. Each row is represented by a string, where each character corresponds to one pixel. The color of pixel is defined by a character's ASCII code, in range from 32 to 126 inclusive.

Space (ASCII 32) corresponds to the background color and is not a color of any rectangle.

Note: When solving this problem in C++, it is recommended to read input data with fgets function for acceptable performance.

Output file format

Output file must contain a single integer: 1 — if the scene exists; 0 — otherwise.

Constraints

Resolution of the input image is no more than 4000 × 4000 pixels.

All input lines have same length.

Sample tests

   *******               @@@@@@@
   *******      ######## @@@@@@@
   *******bbbbb //////// @@@@@@@
          bbbbb //////// @@@@@@@
yy   .....bbbbb ////////        
yy   .....      ########        
yy   .....      ########00000   
yy   .....      ########00000   
                ########00000   
ttttxxxxxxxxxxx     000000000   
ttttxxxxxxxxxxx ====000000000===
ttttUUUUUUxxxxx ====000000000===
    UUUUUUxxxxx ====000000000===
    UUUUUUxxxxx ====000000000===
    UUUUUU      ================
    UUUUUU                      

1

xxxx       xxxxxxxx@@@@@@@@@    
xxxx  aaa  xxxxxxxx@@@@@@@@@    
xxxx       xxxxxxxx@@@@@@@@@    
xxxx  xxx                xxxxxxx
xxxx  xxx                xxxxxxx
xxxx       xxxxxxxx      #######
xxxx    ===xx======   xxx#######
xxxx    ===xx======   xxx#######
xxxx    ===xx======   xxx///////
xxxx    ===xxxxxxxx   xxx///////
        ===========      ///////
    xxxx===========      xxxxxxx
    xxxx===========      xxxxxxx
    xxxx===========      xxxxxxx
    xxxxxxxxxxxxxxxxxxxx        
    xxxxxxxxxxxxxxxxxxxx        

0

Problem D. Directory synchronization ≡

Statement

Consider the directory that contains files. Names of these files are composed from Latin letters (uppercase A-Z and lowercase a-z letters are distinct), digits, such characters as '-' (ASCII 45), '.' (ASCII 46) and spaces (ASCII 32). Different files have different names.

Initial content of any file is unique. In future it can not be changed, but it can be copied to a new file.

There is need to periodically synchronize the local version of this directory with its backup copy that is placed on remote server. In this case the previous version of the remote directory must be updated to the current state with minimal computational costs.

For this purpose all operations that are performed in the local directory are stored to in a special log, in historical order. This log contains records in following forms:

• cpy "source" "target" — file "source" was copied to "target";
• mov "source" "target" — file "source" was moved to "target";
• new "target" — file "target" was created;
• del "target" — file "target" was deleted.

It is known that these operations cause error if:

• the source that is specified for cpy or mov does not exist;
• the target that is specified for cpy, mov or new exists;
• the target that is specified for del does not exist.

To update of the remote directory, we must apply similar operations to it. In this case each of them has a certain cost: for mov and del it is 1, cost of cpy is 10.

Also we assume that operation new means to copy a file from the local directory to remote server and has cost is 100.

Your program must, given the initial state of remote directory and set of records of the log, obtain sequence of the operations with minimal total cost that allow to make update of the backup copy to the current state. These operations must not cause errors.

Special file name "~" (ASCII 126) is considered acceptable by remote server, but is not used by operations in the log. It is recommended to use this name for temporary file copies.

Input file format

Input file contains integer N — initial number of files in the directory, followed by the N file names enclosed in double quotes, one name per line.

After that, input file contains integer M — number of the records of the log, followed by M log records, one record per line.

All file names are enclosed in double quotes.

Output file format

Output file must contain integer L — number of the operations, followed by L operations in the same format as log records, one operation per line.

All file names must be enclosed in double quotes.

Constraints

File names have length from 1 to 16 characters. Operations in the log do not cause errors.

0 ≤ N, M ≤ 10⁴

Sample tests

5
"BaNaNa-145"
"Example-01"
"MyMusic-03"
"MyGame.exe"
"UNIT.1.pas"

10
mov "MyMusic-03" "BestMusic.mp3"
mov "MyGame.exe" "F0"
mov "BaNaNa-145" "MyMusic-03"
del "Example-01"
cpy "UNIT.1.pas" "UNIT.2.pas"
del "UNIT.1.pas"
mov "F0" "BaNaNa-145"
new "x2"
mov "BestMusic.mp3" "MyGame.exe"
new "UNIT.1.pas"

8
mov "BaNaNa-145" "~"
mov "MyGame.exe" "BaNaNa-145"
mov "MyMusic-03" "MyGame.exe"
mov "~" "MyMusic-03"
del "Example-01"
mov "UNIT.1.pas" "UNIT.2.pas"
new "x2"
new "UNIT.1.pas"

5
"BaNaNa-145"
"Example-01"
"MyMusic-03"
"MyGame.exe"
"UNIT.1.pas"

10
mov "BaNaNa-145" "BaNaNa-360"
cpy "MyMusic-03" "M0"
cpy "BaNaNa-360" "NaN.InF"
mov "NaN.InF" "BaNaNa-145"
new "x2"
del "BaNaNa-360"
mov "M0" "Music.mp3"
del "MyMusic-03"
mov "Music.mp3" "MyMusic-03"
del "x2"

0

Problem E. Expression with period ≡

Statement

An expression for a function is composed of single-digit numbers, variable x, signs + and *, and zero or one calls to function sin. More formally:

• expression ::= 0|1|2|3|4|5|6|7|8|9|x
• expression ::= expression+expression
• expression ::= expression*expression
• expression ::= sin(expression)

Function f(x) has period p if f(x+p) = f(x) for all x.

Your program must, given an expression with no more than one call to sin, determine the minimal period of a function.

Input file format

The input file contains a single string — expression.

Output file format

Output file must contain single a floating point number — period with relative error not greater than 10⁻⁶. If a function is constant or aperiodic, output number 0.

Constraints

Expression length is between 1 and 25 characters. There are no spaces in expression.

Sample tests

sin(x)+x

0

5*6*sin(2*x+5+x*7+x)+1

0.62831853

sin(x*0)

0

Problem F. Fibonacci level ≡

Statement

For arbitrary non-empty strings S₁ and S₂, the Fibonacci sequence of strings is defined by a recurrence S_i+2 = S_i+1 + S_i, where the '+' sign denotes string concatenation.

Let's say that string T has Fibonacci level n if there exists some Fibonacci sequence of strings which contains S_n = T. Note that any string of length 2 or more has Fibonacci level 3.

Your program must, given a string T, find its maximum Fibonacci level n as well as two starting strings S₁ and S₂ of corresponding Fibonacci sequence of strings.

Input file format

Input file contains a single string T, consisting of lowercase Latin letters.

Output file format

Output file must contain 3 lines: integer n followed by strings S₁ and S₂.

If there are several optimal solutions, output any of them.

Constraints

2 ≤ |T| ≤ 10⁶

Sample tests

oxax

3
xax
o

cabccab

5
ab
c

axaxax

4
ax
ax

Problem G. Group by the bus ≡

Statement

N delegations arrived for the ACM ICPC quarterfinals. Delegation i consists of a_i people.

The organizers were able to find M buses to deliver the contestants from the hotel to the university. Bus j has enough place for b_j people.

Settling the delegations into buses was entrusted to Masha — the most responsible member of the organizing committee. However, that was done in the very last day, which resulted in the following:

• The buses will arrive in a particular order which Masha can't control.
• Each bus leaves before the next one arrives.
• Delegations will queue at the bus stop in a particular order that Masha can't control.
• A delegation may start to take seats only after all delegations in front of it in the queue are seated.

Contestants from each delegation prefer to stay together. But unfortunately some delegations may have to split into groups to fit into the buses. Masha wants to help the teams to form the least number of groups that will fit in the buses, given the constraints above (if a delegation is not split, it counts as 1 group).

Your program must allocate bus seats to contestants in a way which minimizes number of groups. It's guaranteed that total amount of people is not more than total capacity of the buses.

Input file format

Input file contains an integer N — number of delegations, followed by N integers a_i — sizes of delegations in the order they queue at the bus stop.

Further follows an integer M — number of buses, followed by M integers b_j — capacities of the buses in the order they arrive.

Output file format

Output file must contain a description for each delegation from 1 to N, in the same order as input.

A description for delegation i starts with a positive integer p_i — the number of groups that the delegation is split into (1 means the delegation is not split at all).

Further, p_i pairs of positive integers must follow. The first integer of each pair is the number of the bus that the group should take (buses are numbered from 1 to M). The second integer is the size of the group. Groups within one delegation should be described in the order of ascending bus numbers.

The number of groups in the output should be minimal possible, given the constrains above. If there is more than one optimal solution, output any of them.

In the sample test #1 there are 3 delegations and 2 buses. The answer contains 4 groups in total (we have to split delegation 2 into 2 groups).

In the sample test #2 the second bus can fit both delegations, no splits required. Note that the first bus leaves completely empty.

Constraints

1 ≤ N, M, a_i, b_j ≤ 100

Sample tests

3
2 4 1
2
4 4

1
1 2
2
1 2
2 2
1
2 1

2
3 4
2
2 10

1
2 3
1
2 4

Problem H. Hierarchical layout ≡

Statement

Young programmer Vasya was recruited by a "WorkMountain" software company. His first assignment was to implement an algorithm which would position a hierarchy of controls on a GUI form according to constraints specified by form designer.

Although Vasya was asked to position controls in two dimensions, he decided to solve one-dimensional problem first.

A control number i is represented by a segment of a line with minimum length A_i, maximum length B_i and has C_i children controls. Controls can be nested to arbitrary depth.

Constraints are simple:

1. actual control length must be between minimum and maximum lengths, inclusive;
2. for every control with one or more children, control length must be exactly equal to the sum of children lengths.

Your program must, given a control (possibly with children) and constraints, assign a length to every control so that every constraint is satisfied.

Input file format

Input file contains integer N — total number of controls, followed by a control description. Each control description contains integers A_i B_i C_i, followed by C_i descriptions of i-th control's children.

Output file format

Output file must contain N integers L_i — lengths of controls in order corresponding to input (A_i ≤ L_i ≤ B_i).

If there is more than one solution, output any of them. If there is no solution, output a single integer −1.

Constraints

1 ≤ N ≤ 1000; 1 ≤ A_i ≤ B_i ≤ 10⁶;

0 ≤ C_i < N; C₁ + C₂ + ⋯ + C_N = N − 1

Sample tests

1
10 20 0

15

3
100 100 2
40 50 0
55 55 0

100 45 55

2
5 6 1
7 8 0

-1

Problem I. Increment and jump ≡

Statement

Young programmer Vasya decided to learn microprocessor design. As a first step, he designed a processor with a single integer register with initial value 0, and two instructions:

• Increment register value by 1 (denoted by letter i).
• Jump back to the beginning of a program (denoted by letter j).

Vasya's friend Petya suggested to modify a design so that after executing jump instruction processor would replace it with a special 'no-op' instruction which does nothing.

Now, Vasya's microprocessor could do something at least a little bit interesting. Vasya wants to write an emulator to explore the possibilities.

Your program must output a value in the register after the execution of a given program for Vasya's microprocessor.

Input file format

The input file contains a single string consisting of letters i and j — a program.

Output file format

Output file must contain single integer — value in the register.

Constraints

Program length is between 1 and 10⁵ characters.

Sample tests

i

1

j

0

ijjijiijji

17

Problem J. Jump or increment? ≡

Statement

Young programmer Vasya decided to learn microprocessor design. As a first step, he designed a processor with a single integer register with initial value 0, and two instructions:

• Increment register value by 1 (denoted by letter i).
• Jump back to the beginning of a program (denoted by letter j).

Vasya's friend Petya suggested to modify a design so that after executing jump instruction processor would replace it with a special 'no-op' instruction which does nothing.

Now, Vasya's microprocessor could do something at least a little bit interesting. Vasya wants to explore low-level optimization for his new microprocessor.

Your program must output a shortest non-empty program for Vasya's microprocessor which would put a given value into the register.

Input file format

Input file contains a single integer N — expected value in the register.

Output file format

Output file must contain a single string consisting of letters i and j — a shortest program to put an expected value into the register.

If there are several shortest programs, output any of them.

Constraints

0 ≤ N ≤ 10⁹.

Sample tests

0

j

1

i

17

ijiiijjj