Problem A. Asphalt ≡

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

10 5 3

19

4 5 3

4

5 5 3

5

Problem B. Box of quarters ≡

Statement

Given a rectangle specified by the coordinates of the lower left corner (x₁, y₁) and the upper right corner (x₂, y₂), 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 x₁, y₁, x₂, y₂.

Output format

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

Constraints

−100 ≤ x₁ < x₂ ≤ 100

−100 ≤ y₁ < y₂ ≤ 100

Sample tests

-3 -3 3 3

4

0 0 100 100

1

Problem C. Circular coverage ≡

Statement

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:

• 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 a_i — 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 ≤ a_i < 36000

Sample tests

4
1 2 18000 18001

35998 2
2 3 4 1 

6
100 200 12000 12100 24000 24100

35700 3
2 3 4 5 6 1 

Problem D. Digital substring ≡

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| ≤ 10⁴

Sample tests

123
5123889

1

58
911453571

3

Problem E. Etintrof ≡

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.

Constraints

1 ≤ N ≤ 500

Sample tests

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 

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 ≡

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 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 format

Input contains integers H, L, and n, followed by n pairs of integers P_i, V_i.

Output format

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

Constraints

0 < (H, L, V_i) ≤ 10⁶, 0 ≤ P_i ≤ 10⁶,

1 ≤ n ≤ 2 ⋅ 10⁵

Sample tests

10 2 4
2 1
3 8
4 7
5 8

2

10 2 4
9 3
8 2
6 3
8 2

0

Problem G. Game with rectangles ≡

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: 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 format

Input contains integer n followed by 4 × n integers: a_i, b_i, c_i and d_i.

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 ≤ 10⁵

−10⁶ ≤ a_i ≤ b_i ≤ 10⁶

−10⁶ ≤ c_i ≤ d_i ≤ 10⁶

Sample tests

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

0
2
3

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 ≡

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.

Constraints

1 ≤ n ≤ 10⁵

Sample tests

5
aaaaa

aazaa

10
asdfghjklz

asdfghjklz

Problem I. Improbable balance ≡

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 10⁻⁷.

Constraints

1 ≤ |S| ≤ 36

Sample tests

())

0.0

(())

1.0

()()()

0.3333333333

Problem J. Jump-herding ≡

Statement

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

• located exactly at point p, or
• is alone,

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 x_i in ascending order.

Output format

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

Constraints

1 ≤ N, C ≤ 10⁵

1 ≤ x_i − 1 ≤ x_i ≤ 10⁹

Sample tests

3 1
1 2 3

3

5 3
1 2 2 3 3

2

Problem K. Kendall ≡

Statement

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 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.

Constraints

1 ≤ N ≤ 10⁵

Sample tests

6

-1

4

4 1 2 3