Author:  M. Sporyshev  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Young road constructor Vasya decided to pave a road with asphalt. The road is a straight line segment L meters long.
Vasya can pave a continuous segment of A meters of road per day. To avoid potential cracks on the borders between segments paved on different days, Vasya decided to overlap segments. Specifically:
Your program must calculate the total number of meters that Vasya will pave.
Input contains three integers L A B.
Output must contain a single integer — the total number of meters paved.
1 ≤ L, A, B ≤ 100
A > B
No.  Standard input  Standard output 

1 


2 


3 


Author:  A. Klenin, I. Blinov  Time limit:  3 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
Given a rectangle specified by the coordinates of the lower left corner (x_{1}, y_{1}) and the upper right corner (x_{2}, y_{2}), your program must determine how many quarters of the coordinate system it intersects with.
A rectangle intersects with the coordinate quarter if at least one of its points lies in it. If the point of the rectangle lies on the OX axis or the OY axis, it is considered that it does not belong to any coordinate quarter.
Input contains four integers x_{1}, y_{1}, x_{2}, y_{2}.
Output must contain a single integer — the number of coordinate quarters intersecting the rectangle.
−100 ≤ x_{1} < x_{2} ≤ 100
−100 ≤ y_{1} < y_{2} ≤ 100
No.  Standard input  Standard output 

1 


2 


Author:  А. Жихарева  Time limit:  2 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
There are N points on a circle, represented by numbers a_{i}, where a_{i} — direction from center to point i, measured in 1/100th parts of degree.
Your program must choose a set of pairs of points so that:
First line of input contains integer N.
Second line contains N integers a_{i} — directions from center to points, measured in 1/100th parts of degree.
Output must contain two integers S and M, where S — largest total arc length, M — number of selected pairs.
Next, output must contain M pairs of integers — pairs of point indices corresponding to the ends of each arc. Indices start with 1. The order of points in pair may be arbitrary.
If there are several optimal solutions, output any of them.
2 ≤ N ≤ 5000, 0 ≤ a_{i} < 36000
No.  Standard input  Standard output 

1 


2 


Author:  А. Жихарева  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Strings S and T consist of digits from 0 to 9.
Let use define transformation step for a string of digits as follows. Select any substring and replace it by the sum of all its digits, as long as that sum does not exceed 9. For example, string 1263 can be transformed into any of 363, 183, 129, 93. String 12345 can be transformed into 339 by two transformation steps.
Your program must count the number of pairs i, j such that 1 ≤ i ≤ j ≤ T and substring of T from ith to jth digit (inclusive) can be transformed into S by some number of steps (including zero).
First line of input contains string S.
Second line of input contains string T.
Output must contain a single integer — the number of pairs.
1 ≤ S, T ≤ 10^{4}
No.  Standard input  Standard output 

1 


2 


Author:  A. Klenin, I. Blinov  Time limit:  3 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
Young programmer Vasya created a twodimensional game in Battle Royale genre. The game is played on a square field of N by N cells. Each cell is either empty (represented by '.') or occupied by wall (represented by '#').
The player is located in one of the empty cells. Every second the player can stay in place or move to an adjacent empty cell up, down, left or right. After player moves, all cells along the perimeter of the game field are removed (so field size is reduced by 2 along each axis). If the player was located on one of the removed cells, he dies.
Your program must, for each empty cell of the field, calculate maximum number of seconds the player can survive if he starts the game from that cell and plays optimally.
The first line of input contains a single integer N. The next N lines contain one string of N characters each — representation of the game field.
The output should contain N lines of N numbers, where the jth number in the ith line indicates the maximum survival time of a player when starting from a cell with coordinates (i, j). If the corresponding cell is not empty, output zero.
1 ≤ N ≤ 500
No.  Standard input  Standard output 

1 


2 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
"Ferryman of Hades" is a simple arcade game based on the Greek mythology. The main scene of the game is Styx river that is represented as a 1dimensional line. Souls fall down from height H to this line. Charon must catch them in his boat when they touch the river line.
The boat of Charon is represented as a closed segment (containing its boundary points) of length L moving along line from the initial position [0, L].
Boat can move only from left to right with a fixed integer speed. It is known that ith soul falls down to point P_{i} with a speed V_{i}.
A soul is caught if by the moment it crosses the river line, this point belongs to the boat.
Your program must, given H, L, P_{i}, and V_{i}, determine the minimum possible integer speed of the boat maximizing the number of caught souls.
Input contains integers H, L, and n, followed by n pairs of integers P_{i}, V_{i}.
Output must contain a single integer — the speed of the boat.
0 < (H, L, V_{i}) ≤ 10^{6}, 0 ≤ P_{i} ≤ 10^{6},
1 ≤ n ≤ 2 ⋅ 10^{5}
No.  Standard input  Standard output 

1 


2 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
Vasya writes a 2D game engine. One of the tasks is to determine parts of the scene visible by the gamer from a given position.
Let us consider a set of rectangles with sides parallel to the coordinate axes: P_{i} = {(x, y): a_{i} ≤ x ≤ b_{i}, c_{i} ≤ y ≤ d_{i}}.
Rectangle P_{i} is visible from the point A, if there exists some point B ∈ P_{i} such that segment AB does not contain points belonging to other rectangles.
Your program must determine indices of rectangles that are visible from the point (0, 0).
Input contains integer n followed by 4 × n integers: a_{i}, b_{i}, c_{i} and d_{i}.
Output must contain indices of visible rectangles in ascending order. Indices start from 0.
Rectangles do not intersect each other and do not contain point (0, 0).
2 ≤ n ≤ 10^{5}
−10^{6} ≤ a_{i} ≤ b_{i} ≤ 10^{6}
−10^{6} ≤ c_{i} ≤ d_{i} ≤ 10^{6}
No.  Standard input  Standard output 

1 


2 


Author:  A. Klenin, I. Blinov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
Elephant Pakhom installed a row of n statues of herons,
each statue is painted in its own color.
Colors are represented by small Latin letters from 'a
' to 'z
'.
The elephant is pleased with the result of his work,
but now he wants to repaint some statues so that there are
no three consecutive statues of the same color.
Since Pakhom has tired during the construction of the statues,
he wants to repaint as few herons as possible.
The first line of the input contains integer n. The second line contains n characters — description of statue colors.
Output must contain a string of length n — a new coloring of herons. If there are several optimal colorings, output any of them.
1 ≤ n ≤ 10^{5}
No.  Standard input  Standard output 

1 


2 


Author:  A. Klenin  Time limit:  3 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
For a string of parentheses '(' and ')', let us define shortening as follows. Pick a random pair of characters '(' and ')' such that '(' is to the left of ')' and delete them. Selection probability is distributed uniformly across all possible pairs. Repeat shortening until no suitable pair left.
Given a string of parentheses, your program must calculate the probability of the above process to finish with an empty string.
Input contains a string of parentheses S.
Output must contain a single floating point number — probability with absolute error of no more than 10^{−7}.
1 ≤ S ≤ 36
No.  Standard input  Standard output 

1 


2 


3 


Author:  М. Спорышев  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Young farmer Alice has N grasshoppers. Grasshoppers sit along the line, ith grasshopper at coordinate x_{i}, measured in centimeters. Several grasshoppers may occupy the same point. A grasshopper is alone, if there is no other grasshopper at its position.
Alice wants to herd grasshoppers into the box which is located at position 0.
To do that, Alice can move to any point p on the line and clap loudly. After each clap, any grasshopper that is either
Once grasshopper reaches the box, it stays there and does not jump anymore.
Your program must determine the minimum number of claps required to get all grasshoppers into the box.
First line of input contains two integers N and C.
Next line contains N integers x_{i} in ascending order.
Output must contain a single integer — the minimum number of claps.
1 ≤ N, C ≤ 10^{5}
1 ≤ x_{i − 1} ≤ x_{i} ≤ 10^{9}
No.  Standard input  Standard output 

1 


2 


Author:  A. Tyshchenko, A. Klenin  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Let X, Y be sequences each consisting of N unique integers and 1 ⩽ x_{i},y_{i}⩽ N. The Kendall correlation coefficient between these sequences is
τ=∑i< jsgn(x_{i}−x_{j})sgn(y_{i}−y_{j}).
sgn(x) = x < 0⇒ −1, x > 0⇒ +1, x = 0⇒ 0.
Suppose that sequence X is 1, 2, …, N. Your program must find sequence Y such that τ(X, Y) = 0.
Input contains a single integer N — number of elements in a sequence.
Output must contain N integers — sequence Y. If the required sequence does not exist, output −1. If there are several solutions, output any of them.
1 ≤ N ≤ 10^{5}
No.  Standard input  Standard output 

1 


2 

