Problem A. Axis of choice ≡

 Author: A. Klenin Time limit: 1 sec Input file: input.txt Memory limit: 256 Mb Output file: output.txt

Statement

A rectangular area with sides parallel to coordinate axises is represented by coordinates of two opposite corners (x1, y1) and (x2, y2).

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

Input file format

Input file contains four integers x1 y1 x2 y2 — 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

109 ≤ x1, y1, x2, y2 ≤ 109

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
30 40 10 20
Y
2
-5 20 -4 -20
X
3
1 1 1 1
XY

Problem B. Boulders ≡

 Author: A. Klenin Time limit: 1 sec Input file: input.txt Memory limit: 256 Mb Output file: output.txt

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.
A pile is stable if all boulders in it are stable.

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.

1 ≤ W, H ≤ 1000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1 2
O
o

.
o

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

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

3
3 3
O.o
.O.
o.O

...
...
o.O


Problem C. Correctness of controller ≡

 Author: A. Baranov Time limit: 1 sec Input file: input.txt Memory limit: 256 Mb Output file: output.txt

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

No. Input file (input.txt) Output file (output.txt)
1
   *******               @@@@@@@
*******      ######## @@@@@@@
*******bbbbb //////// @@@@@@@
bbbbb //////// @@@@@@@
yy   .....bbbbb ////////
yy   .....      ########
yy   .....      ########00000
yy   .....      ########00000
########00000
ttttxxxxxxxxxxx     000000000
ttttxxxxxxxxxxx ====000000000===
ttttUUUUUUxxxxx ====000000000===
UUUUUUxxxxx ====000000000===
UUUUUUxxxxx ====000000000===
UUUUUU      ================
UUUUUU                      
1
2
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 ≡

 Author: A. Baranov Time limit: 1 sec Input file: input.txt Memory limit: 256 Mb Output file: output.txt

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 ≤ 104

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
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"

2
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 ≡

 Author: A. Klenin Time limit: 1 sec Input file: input.txt Memory limit: 256 Mb Output file: output.txt

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

No. Input file (input.txt) Output file (output.txt)
1
sin(x)+x
0
2
5*6*sin(2*x+5+x*7+x)+1
0.62831853
3
sin(x*0)
0

Problem F. Fibonacci level ≡

 Author: M. Sporyshev, A. Klenin, A. Baranov Time limit: 1 sec Input file: input.txt Memory limit: 256 Mb Output file: output.txt

Statement

For arbitrary non-empty strings S1 and S2, the Fibonacci sequence of strings is defined by a recurrence Si+2 = Si+1 + Si, 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 Sn = 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 S1 and S2 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 S1 and S2.

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

2 ≤ |T| ≤ 106

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
oxax
3
xax
o
2
cabccab
5
ab
c

3
axaxax
4
ax
ax

Problem G. Group by the bus ≡

 Author: M. Sporyshev Time limit: 1 sec Input file: input.txt Memory limit: 256 Mb Output file: output.txt

Statement

N delegations arrived for the ACM ICPC quarterfinals. Delegation i consists of ai 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 bj 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 ai — sizes of delegations in the order they queue at the bus stop.

Further follows an integer M — number of buses, followed by M integers bj — 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 pi — the number of groups that the delegation is split into (1 means the delegation is not split at all).

Further, pi 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, ai, bj ≤ 100

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
2 4 1
2
4 4

1
1 2
2
1 2
2 2
1
2 1

2
2
3 4
2
2 10

1
2 3
1
2 4


Problem H. Hierarchical layout ≡

 Author: A. Klenin Time limit: 1 sec Input file: input.txt Memory limit: 256 Mb Output file: output.txt

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 Ai, maximum length Bi and has Ci 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 Ai Bi Ci, followed by Ci descriptions of i-th control's children.

Output file format

Output file must contain N integers Li — lengths of controls in order corresponding to input (Ai ≤ Li ≤ Bi).

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 ≤ Ai ≤ Bi ≤ 106;

0 ≤ Ci < N; C1 + C2 + ⋯ + CN = N − 1

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1
10 20 0

15

2
3
100 100 2
40 50 0
55 55 0

100 45 55

3
2
5 6 1
7 8 0

-1

Problem I. Increment and jump ≡

 Author: A. Klenin Time limit: 1 sec Input file: input.txt Memory limit: 256 Mb Output file: output.txt

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 quickly noticed that this instruction set is not very useful, because any program containing even one jump instruction will loop forever.

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 105 characters.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
i
1
2
j
0
3
ijjijiijji
17

Problem J. Jump or increment? ≡

 Author: A. Klenin Time limit: 1 sec Input file: input.txt Memory limit: 256 Mb Output file: output.txt

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 quickly noticed that this instruction set is not very useful, because any program containing even one jump instruction will loop forever.

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.

0 ≤ N ≤ 109.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
0
j
2
1
i
3
17
ijiiijjj

0.307s 0.011s 25