Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
A rectangular area with sides parallel to coordinate axises is represented by coordinates of two opposite corners (x_{1}, y_{1}) and (x_{2}, y_{2}).
Your program must find the coordinate axis which is closest to the given rectangular area.
Input file contains four integers x_{1} y_{1} x_{2} y_{2} — coordinates of area corners.
Output file must contain a single string:
−10^{9} ≤ x_{1}, y_{1}, x_{2}, y_{2} ≤ 10^{9}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
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:
Your program must remove minimal possible number of boulders from the pile so that the pile becomes stable.
First line of input contains integers W H. Following H lines contain W characters each — pile representation.
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
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
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 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 must contain a single integer: 1 — if the scene exists; 0 — otherwise.
Resolution of the input image is no more than 4000 × 4000 pixels.
All input lines have same length.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Consider the directory that contains files. Names of these files are composed from Latin letters (uppercase AZ and lowercase az 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:
It is known that these operations cause error if:
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 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 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.
File names have length from 1 to 16 characters. Operations in the log do not cause errors.
0 ≤ N, M ≤ 10^{4}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
An expression for a function is composed of singledigit numbers, variable x, signs + and *, and zero or one calls to function sin. More formally:
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.
The input file contains a single string — expression.
Output file must contain single a floating point number — period with relative error not greater than 10^{−6}. If a function is constant or aperiodic, output number 0.
Expression length is between 1 and 25 characters. There are no spaces in expression.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


Author:  M. Sporyshev, A. Klenin, A. Baranov  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
For arbitrary nonempty strings S_{1} and S_{2}, 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_{1} and S_{2} of corresponding Fibonacci sequence of strings.
Input file contains a single string T, consisting of lowercase Latin letters.
Output file must contain 3 lines: integer n followed by strings S_{1} and S_{2}.
If there are several optimal solutions, output any of them.
2 ≤ T ≤ 10^{6}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


Author:  M. Sporyshev  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
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:
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 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 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.
1 ≤ N, M, a_{i}, b_{j} ≤ 100
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
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 onedimensional 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:
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 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 ith control's children.
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.
1 ≤ N ≤ 1000; 1 ≤ A_{i} ≤ B_{i} ≤ 10^{6};
0 ≤ C_{i} < N; C_{1} + C_{2} + ⋯ + C_{N} = N − 1
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
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:
Vasya's friend Petya suggested to modify a design so that after executing jump instruction processor would replace it with a special 'noop' 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.
The input file contains a single string consisting of letters i and j — a program.
Output file must contain single integer — value in the register.
Program length is between 1 and 10^{5} characters.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
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:
Vasya's friend Petya suggested to modify a design so that after executing jump instruction processor would replace it with a special 'noop' instruction which does nothing.
Now, Vasya's microprocessor could do something at least a little bit interesting. Vasya wants to explore lowlevel optimization for his new microprocessor.
Your program must output a shortest nonempty program for Vasya's microprocessor which would put a given value into the register.
Input file contains a single integer N — expected value in the register.
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 ≤ 10^{9}.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 

