Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  64 Mb  
Output file:  output.txt 
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.
1 ≤ N ≤ 2^{31} − 1
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Klenin  Time limit:  2 sec  
Input file:  input.txt  Memory limit:  64 Mb  
Output file:  output.txt 
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 32bit unsigned integers in the littleendian 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.
0 ≤ a, b, N, a + N × b ≤ 2^{32} − 1
0 ≤ N ≤ 5 × 10^{6}
Bit string consists of 1 to 32 bits.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


Author:  A. Klenin  Time limit:  2 sec  
Input file:  input.txt  Memory limit:  64 Mb  
Output file:  output.txt 
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 a_{1}, …, a_{N} and will have to perform M concatenations represented by pairs of integers (p_{1}, q_{1}), …, (p_{M}, q_{M}). Each pair (p_{j}, q_{j}) means that a new string a_{N + j} is the concatenation of strings a_{pj} and a_{qj}, where 1 ≤ p_{j}, q_{j} < 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 a_{N + M} from position L to position R, counting from 1.
1 ≤ N ≤ 1000, 1 ≤ M ≤ 1000,
1 ≤ length(a_{i}) ≤ 1000 for i = 1, N,
1 ≤ length(a_{N + j}) ≤ 2 × 10^{9} for j = 1, M,
1 ≤ L ≤ R ≤ length(a_{N + M}),
R − L + 1 ≤ 1000.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Klenin  Time limit:  2 sec  
Input file:  input.txt  Memory limit:  64 Mb  
Output file:  output.txt 
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:
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.
First line of input file contains integers N_{1} N_{2} M. Following lines contain N_{1} locking primitives called by the first task, then N_{2} 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 must contain integers D_{1} D_{2}, designating that deadlock can occur when the first task is trying to execute primitive number D_{1} (1 ≤ D_{1} ≤ N_{1}) while the second task is trying to execute primitive number D_{2} (1 ≤ D_{2} ≤ N_{2}).
If there is more than one possible deadlock, output the one with minimal D_{1}. If there is still more then one, output the one with minimal D_{2}. If the deadlock is not possible, output file must contain a single 0 (zero).
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  I. Ludov, A. Klenin  Time limit:  2 sec  
Input file:  input.txt  Memory limit:  64 Mb  
Output file:  output.txt 
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 A′AC and B′BC are viewing angles, and the second of them is the maximum one.
Input file contains the number of monitors N followed by N triplets of integers x_{i} y_{i} a_{i}, where x_{i} y_{i} — coordinates of room vertexes in counterclockwise order, a_{i} = 1 if the wall between the ith vertex and the next one is covered by a monitor, a_{i} = 0 otherwise.
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).
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  64 Mb  
Output file:  output.txt 
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", "12345e1" 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 number contains from 1 to 1000 digits and is either 0 or in range from 10^{ − 2000} to 10^{2000}.
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'.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


4 


5 


6 


Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  64 Mb  
Output file:  output.txt 
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 Kth cell". In the latter case, the player immediately moves to the Kth 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.
2 ≤ N ≤ 25, d_{1} = d_{N} = d_{di} = 0
There is always at least one sequence of dice throws allowing to finish the game.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


Author:  A. Klenin  Time limit:  2 sec  
Input file:  input.txt  Memory limit:  64 Mb  
Output file:  output.txt 
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 twodimensional 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.
1 ≤ N, M ≤ 50
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 

