## Problem A. As simple as it gets ≡

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

### Statement

Let us define that a positive integer A is simpler than a positive integer B if the decimal representation of A requires less different digits than the decimal representation of B.

For example, number 55 is simpler than 12 which in turn is simpler than 123.

Your program will be given a number N and must find the largest integer X such that X < N and X is simpler than N.

### Input file format

Input file contains integer N.

### Output file format

Output file must contain integer X. If there is no integer simpler than N, output file must contain 0 (zero).

1 ≤ N ≤ 231 − 1

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
111
0
2
765437654
765377777

## Problem B. Bit by bit ≡

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

### Statement

Some applications (such as compression algorithms) require searching a memory area for arbitrary bit strings.

Your program must find the first occurrence of the given bit string in the sequence of numbers generated by an arithmetic progression: a, a + b, a + 2 b, …, a + N × b. Numbers are stored in a continuous memory area as 32-bit unsigned integers in the little-endian byte order. Bits in byte are counted from the least significant to the most significant one.

For example, number 123456 will be stored as a sequence of four bytes with hexadecimal values "40 E2 01 00", interpreted as bit string "00000010 01000111 10000000 00000000" (spaces inserted for readability only). So the occurrence of the bit substring "1001" would be at position 7.

Note that the occurrence can cross boundaries between numbers.

### Input file format

First line of input file contains integers a b N. Second line of input file contains a string of '0' and '1' characters, each character representing one bit of the string to search for.

### Output file format

Output file must contain a single integer — the position of the bit string in the memory area, starting from 1. If the bit string is not found, output file must contain 0 (zero).

### Constraints

0 ≤ a, b, N, a + N × b ≤ 232 − 1

0 ≤ N ≤ 5 × 106

Bit string consists of 1 to 32 bits.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1 1 1
1
1
2
0 1 1
001
31
3
1 2 11
111
97

## Problem C. Concatenation ≡

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

### Statement

String concatenation is the operation of joining two character strings end to end. For example, the strings "foo" and "bar" may be concatenated to give "foobar".

You program will be given N strings a1, …, aN and will have to perform M concatenations represented by pairs of integers (p1, q1), …, (pM, qM). Each pair (pj, qj) means that a new string aN + j is the concatenation of strings apj and aqj, where 1 ≤ pj, qj < N + j.

For example, strings "a" and "bc" and pairs (1, 2), (3, 3) mean that new strings "abc" and "abcabc" are generated.

Your program must output a substring of aN + M from position L to position R, counting from 1.

### Input file format

First line of input file contains integers N M L R. Following N lines contain strings ai — one string per line. Each of the following M lines contain two integers pj qj.

### Output file format

Output file must contain a string of R − L + 1 characters.

### Constraints

1 ≤ N ≤ 1000, 1 ≤ M ≤ 1000,

1 ≤ length(ai) ≤ 1000 for i = 1, N,

1 ≤ length(aN + j) ≤ 2 × 109 for j = 1, M,

1 ≤ L ≤ R ≤ length(aN + M),

R − L + 1 ≤ 1000.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2 2 3 6
a
bc
1 2
3 3
cabc
2
1 5 1 32
z
1 1
2 2
3 3
4 4
5 5
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz

## Problem D. Deadlock detector ≡

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

### Statement

Resource sharing is an important problem in parallel programming. When parallel tasks must use common resource, such as input/output channel, they serialize their access by using locks.

Two basic locking primitives are provided:

• LOCK r — marks resource as locked by the calling task. If the resource is already locked by the same task, it does nothing. If it is locked by a different task, calling task is blocked (i.e. pauses execution and waits) until the resource is unlocked.
• UNLOCK r — unlocks given resource if it is locked by the current task, and does nothing otherwise.

After the execution of the last locking primitive of the task, all resources locked by that task are unlocked.

Locking guarantees that only a single task can access the resource at a time. However, carelessly written programs may still lead to some unfortunate situations. If task A has already locked resource P and tries to lock Q, while task B has already locked Q and tries to lock P, they will both wait endlessly. This condition is called "deadlock".

Your program must, given lock/unlock sequences executed by two parallel tasks while accessing M resources, determine whether a deadlock is possible between them.

### Input file format

First line of input file contains integers N1 N2 M. Following lines contain N1 locking primitives called by the first task, then N2 primitives called by the second task, in the order of calling.

Each primitive is located on a separate line and consists of a string LOCK or UNLOCK followed by one or more spaces and a resource number r (1 ≤ r ≤ M).

### Output file format

Output file must contain integers D1 D2, designating that deadlock can occur when the first task is trying to execute primitive number D1 (1 ≤ D1 ≤ N1) while the second task is trying to execute primitive number D2 (1 ≤ D2 ≤ N2).

If there is more than one possible deadlock, output the one with minimal D1. If there is still more then one, output the one with minimal D2. If the deadlock is not possible, output file must contain a single 0 (zero).

### Constraints

1 ≤ N1, N2 ≤ 5000, 1 ≤ M≤ 100.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2 2 2
LOCK 1
LOCK 2
LOCK 2
LOCK 1
2 2
2
3 3 5
LOCK 5
LOCK 2
LOCK 3
LOCK 5
LOCK 3
LOCK 2
0

## Problem E. Eye of the Admin ≡

 Author: I. Ludov, A. Klenin Time limit: 2 sec Input file: input.txt Memory limit: 64 Mb Output file: output.txt

### Statement

Young system administrator Vasya is moving into a new server room. The room has a shape of convex polygon with LCD monitors mounted on some of the walls.

Monitors display the health data of various servers, so Vasya wishes to place his rotating chair such that he could observe them all without need to leave it. He moved all obstacles out of the way, so he can see any point of any monitor from any place inside the room. The only problem is that the image on LCD monitors deteriorates at large viewing angles.

Viewing angle is an angle between the line connecting the eye of viewer with the point on monitor and the normal vector at that point. The angle can have values in range from 0 to π  / 2. Vasya wants to place his chair at a point which minimizes a maximum viewing angle from him to any point of any monitor.

For example, in a picture line segment AB represents a monitor, point C — a chair, angles AAC and BBC are viewing angles, and the second of them is the maximum one.

### Input file format

Input file contains the number of monitors N followed by N triplets of integers xi yi ai, where xi yi — coordinates of room vertexes in counter-clockwise order, ai = 1 if the wall between the i-th vertex and the next one is covered by a monitor, ai = 0 otherwise.

### Output file format

Output file must contain floating point values x y — coordinates of point to place a chair. The point must lie inside the room.

If there is more than one solution, output any of them. The maximum viewing angle from point (x, y) must differ from the correct answer by at most 10 − 3 (measured in radians).

### Constraints

3 ≤ N ≤ 40, 1 ≤ Σ ai ≤ 10, 0 ≤ xi, yi ≤ 105.

### Sample tests

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

## Problem F. Floating formatting ≡

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

### Statement

Floating point numbers can be presented by a computer program in various formats, either exponential or fixed. For example, a number 1234.5 can be presented as "1234.5", "123.45e1", "0.12345e4", "12345e-1" and so on.

You program must find the shortest possible representation of a given floating point number. Representation is allowed to omit both leading and trailing zeros, but must preserve all the other digits.

### Input file format

Input file contains a single floating point number. Note that it may be too long to be stored in built-in floating point types without loss of precision.

### Output file format

Output file must contain a single string — the shortest representation of the input number. If there is more than one shortest representation, you must choose the one in fixed format, or, failing that, the one with the lowest absolute value of exponent.

### Constraints

Input number contains from 1 to 1000 digits and is either 0 or in range from 10 − 2000 to 102000.

Both input and output numbers must contain at least one digit on each side of the decimal point (if the point is present) and must denote exponent with the lowercase letter 'e'.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
001e-1
0.1
2
1e-002
0.01
3
0.001
1e-3
4
12000
12e3
5
12345e-4
1.2345
6
15e-10
1.5e-9

## Problem G. Girl's game ≡

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

### Statement

Young programmer Vasya has a little sister. She likes to play tabletop games, and constantly nags her brother to play with her.

One game she particularly enjoys is played with a dice and a long board. The board is divided into a sequence of N cells. A player starts from the first cell. Each turn, the player throws the dice, obtaining an evenly distributed random number from 1 to 6. The player advances forward by the number of cells equal to the number on the dice. Destination cell is either empty, or contains instruction "jump to the K-th cell". In the latter case, the player immediately moves to the K-th cell instead of the destination cell.

The game ends when the number on the dice is equal to or greater than the number of cells left to the end of the board.

Vasya finds the game rather boring, especially the fact that the instructions on the cells keep sending you back again and again, dragging the game indefinitely.

Vasya wants to calculate the expected value (also known as the mathematical expectation) of the number of moves, so he could estimate the average time required to finish the game.

### Input file format

Input file contains an integer N, followed by N integers di, where di = 0 if the cell is empty or contains the number of cell (from 1 to N − 1) where the player must move instead of the i-th cell.

### Output file format

Output file must contain a single floating point number — expected value of the number of turns with the absolute error of at most 10 − 3.

### Constraints

2 ≤ N ≤ 25, d1 = dN = ddi = 0

There is always at least one sequence of dice throws allowing to finish the game.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2 0 0
1
2
3 0 0 0
1.166667
3
3 0 1 0
1.2

## Problem H. H2O and other slogans ≡

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

### Statement

When young programmer Vasya was even younger, he found a book on organic chemistry. He did not understand a thing, but liked the pictures of structural chemical formulae in the book and started to draw many similar ones.

Years later, while clearing his room, Vasya found his old drawings and wondered which of them were correct. Since there were many of them, he decided to write a program for that task. The structural formula of a chemical compound is a graphical representation of the molecular structure showing how the atoms are arranged. Atoms are denoted by letters, and chemical bonds between them — by line segments.

Formula is represented in input file as a two-dimensional array of characters. Each character may be: '.' (ASCII 46) — empty space, 'C' — carbon atom, 'H' — hydrogen atom, 'O' — oxygen atom, '|' (ASCII 124), '/' (ASCII 47), '\' (ASCII 92), '-' (ASCII 45) — chemical bonds. Bonds in correct formula are drawn as straight vertical, horizontal or diagonal lines without intersections. Atoms represented by adjacent letters are not considered bonded.

Correct formula must contain at least one atom and must be connected (there must be a path from each atom to each other passing through bonds).

Additionally, Vasya wants to check that the number of bonds for each atom is equal to the valency number of the corresponding chemical element. For simplicity, he decided that number would be always equal to 4 for carbon, 2 for oxygen and 1 for hydrogen.

### Input file format

First line of input file contains integers N M. Following N lines contain M characters each — formula representation.

### Output file format

Output file must contain a single string: GOOD, if the drawing represents correct formula, VALENCY if the formula is correct in everything except valencies, and BAD otherwise.

1 ≤ N, M ≤ 50

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2 3
-C|
..|
BAD
2
3 6
..HH..
./..\.
O----O
GOOD
3
3 6
H--C..
....\.
.....H
VALENCY

0.673s 0.012s 31