## Problem A. Asphalt ≡

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

### Statement

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:

• On the first day, Vasya paves first A meters.
• On the second day, Vasya moves back B meters, and paves A meters starting from that point.
• This process is repeated until the whole road is paved.
• Vasya stops paving as soon as the last meter of the road is paved, even if he paved less than A meters at the last day.

Your program must calculate the total number of meters that Vasya will pave.

### Input format

Input contains three integers L A B.

### Output format

Output must contain a single integer — the total number of meters paved.

### Constraints

1 ≤ L, A, B ≤ 100

A > B

### Sample tests

No. Standard input Standard output
1
10 5 3
19
2
4 5 3
4
3
5 5 3
5

## Problem B. Box of quarters ≡

 Author: A. Klenin, I. Blinov Time limit: 3 sec Input file: Standard input Memory limit: 256 Mb Output file: Standard output

### Statement

Given a rectangle specified by the coordinates of the lower left corner (x1, y1) and the upper right corner (x2, y2), 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 format

Input contains four integers x1, y1, x2, y2.

### Output format

Output must contain a single integer — the number of coordinate quarters intersecting the rectangle.

### Constraints

100 ≤ x1 < x2 ≤ 100

100 ≤ y1 < y2 ≤ 100

### Sample tests

No. Standard input Standard output
1
-3 -3 3 3
4
2
0 0 100 100
1

## Problem C. Circular coverage ≡

 Author: А. Жихарева Time limit: 2 sec Input file: Standard input Memory limit: 512 Mb Output file: Standard output

### Statement

There are N points on a circle, represented by numbers ai, where ai — 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:

• Each pair of points defines an arc of a circle, shorter of two possible arcs.
• For a pair of points lying on the diameter, it is allowed to choose any of the arcs.
• Each point belongs to at most one pair.
• Arcs defined by different pairs do not have common points.
• The total length of all arcs, measured in 1/100th parts of degree, is as large as possible.

### Input format

First line of input contains integer N.

Second line contains N integers ai — directions from center to points, measured in 1/100th parts of degree.

### Output format

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.

### Constraints

2 ≤ N ≤ 5000, 0 ≤ ai < 36000

### Sample tests

No. Standard input Standard output
1
4
1 2 18000 18001

35998 2
2 3 4 1 
2
6
100 200 12000 12100 24000 24100
35700 3
2 3 4 5 6 1 

## Problem D. Digital substring ≡

 Author: А. Жихарева Time limit: 1 sec Input file: Standard input Memory limit: 512 Mb Output file: Standard output

### Statement

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 i-th to j-th digit (inclusive) can be transformed into S by some number of steps (including zero).

### Input format

First line of input contains string S.

Second line of input contains string T.

### Output format

Output must contain a single integer — the number of pairs.

### Constraints

1 ≤ |S|, |T| ≤ 104

### Sample tests

No. Standard input Standard output
1
123
5123889
1
2
58
911453571
3

## Problem E. Etintrof ≡

 Author: A. Klenin, I. Blinov Time limit: 3 sec Input file: Standard input Memory limit: 256 Mb Output file: Standard output

### Statement

Young programmer Vasya created a two-dimensional 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.

### Input format

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.

### Output format

The output should contain N lines of N numbers, where the j-th number in the i-th 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

### Sample tests

No. Standard input Standard output
1
5
.....
.....
.....
.....
.....
1 2 3 2 1
2 3 3 3 2
3 3 3 3 3
2 3 3 3 2
1 2 3 2 1 
2
5
.....
.#.#.
.....
.#.#.
.....
1 1 3 1 1
1 0 3 0 1
3 3 3 3 3
1 0 3 0 1
1 1 3 1 1 

## Problem F. Ferryman of Hades ≡

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

### Statement

"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 1-dimensional 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 i-th soul falls down to point Pi with a speed Vi.

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, Pi, and Vi, determine the minimum possible integer speed of the boat maximizing the number of caught souls.

### Input format

Input contains integers H, L, and n, followed by n pairs of integers Pi, Vi.

### Output format

Output must contain a single integer — the speed of the boat.

### Constraints

0 < (H, L, Vi) ≤ 106, 0 ≤ Pi ≤ 106,

1 ≤ n ≤ 2 ⋅ 105

### Sample tests

No. Standard input Standard output
1
10 2 4
2 1
3 8
4 7
5 8

2
2
10 2 4
9 3
8 2
6 3
8 2

0

## Problem G. Game with rectangles ≡

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

### Statement

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: Pi = {(x, y): ai ≤ x ≤ bi, ci ≤ y ≤ di}.

Rectangle Pi is visible from the point A, if there exists some point B ∈ Pi 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 format

Input contains integer n followed by 4 × n integers: ai, bi, ci and di.

### Output format

Output must contain indices of visible rectangles in ascending order. Indices start from 0.

### Constraints

Rectangles do not intersect each other and do not contain point (0, 0).

2 ≤ n ≤ 105

106 ≤ ai ≤ bi ≤ 106

106 ≤ ci ≤ di ≤ 106

### Sample tests

No. Standard input Standard output
1
5
-3  3 -2 -1
2  8  4  6
1  4  2  3
-4 -1  2  8
1  7 -5 -3

0
2
3

2
5
0  4  3  7
-1  2  1  2
1  5 -3 -2
0  0 -6 -5
0  0 -4 -2

1
2
4


## Problem H. Heron statues ≡

 Author: A. Klenin, I. Blinov Time limit: 1 sec Input file: Standard input Memory limit: 256 Mb Output file: Standard output

### Statement

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.

### Input format

The first line of the input contains integer n. The second line contains n characters — description of statue colors.

### Output format

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

### Sample tests

No. Standard input Standard output
1
5
aaaaa
aazaa
2
10
asdfghjklz
asdfghjklz

## Problem I. Improbable balance ≡

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

### Statement

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 format

Input contains a string of parentheses S.

### Output format

Output must contain a single floating point number — probability with absolute error of no more than 107.

1 ≤ |S| ≤ 36

### Sample tests

No. Standard input Standard output
1
())
0.0
2
(())
1.0
3
()()()
0.3333333333

## Problem J. Jump-herding ≡

 Author: М. Спорышев Time limit: 1 sec Input file: Standard input Memory limit: 512 Mb Output file: Standard output

### Statement

Young farmer Alice has N grasshoppers. Grasshoppers sit along the line, i-th grasshopper at coordinate xi, 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

• located exactly at point p, or
• is alone,
jumps C centimeters to the left.

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.

### Input format

First line of input contains two integers N and C.

Next line contains N integers xi in ascending order.

### Output format

Output must contain a single integer — the minimum number of claps.

### Constraints

1 ≤ N, C ≤ 105

1 ≤ xi − 1 ≤ xi ≤ 109

### Sample tests

No. Standard input Standard output
1
3 1
1 2 3
3
2
5 3
1 2 2 3 3
2

## Problem K. Kendall ≡

 Author: A. Tyshchenko, A. Klenin Time limit: 1 sec Input file: Standard input Memory limit: 512 Mb Output file: Standard output

### Statement

Let X, Y be sequences each consisting of N unique integers and 1 ⩽ xi,yi⩽ N. The Kendall correlation coefficient between these sequences is

τ=ijsgn(xixj)sgn(yiyj).

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 format

Input contains a single integer N — number of elements in a sequence.

### Output format

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

### Sample tests

No. Standard input Standard output
1
6
-1
2
4
4 1 2 3

0.795s 0.011s 37