Problem A. Any number ≡

Statement

Vasya has three integers: A, B and C, initially number C is equal to zero.

He can use two following operations any number of times.

1) Add number A to number C.

2) Subtract number B from number C.

Vasya also has some integer X (possibly negative) and wants to get it from number C.

Determine if this is always possible or not?

Input format

First line contains 2 integers: A and B.

Output format

Answer to the problem - YES or NO.

Constraints

0 ≤ A ≤ 500

0 ≤ B ≤ 500

Notes on samples

In first example Vasya can get any integer number.

In second example it is impossible to get number 14.

Sample tests

312 353

YES

102 357

NO

Problem B. Bearded joke ≡

Statement

Some kind of an old joke: Letter to the Balabanovo Match Factory. "I constantly count the matches in your boxes — they are 59, then 60, and sometimes 58. Are you all crazy there or something???"

Obsessed pensioner Oderyozhimov made another control purchase of k ? 2 boxes of matches. His fears were confirmed—all the boxes contained a different number of matches, and again they turned out to be consecutive natural numbers. The old man admired the beautiful equilateral triangle folded from all the matches with a side of n, divided into unit triangles, and began his next letter.

Input format

The only line of input contains a natural number: n — the side of the triangle.

Output format

Output a single natural number — the number of different suitable values for k.

Constraints

1 ≤ n ≤ 500000

Example explanation

In the example, n = 4 is given (see the picture). In the resulting figure, exactly 30 matches.

The pensioner could buy three boxes with 9, 10, and 11 matches.

He could buy four boxes with 6, 7, 8, and 9 matches.

Or he could buy five boxes with 4, 5, 6, 7, and 8 matches.

There are no other suitable solutions.

Sample tests

4

3

Problem C. Cutpoint on the plane ≡

Statement

Doctors of a city polyclinic faced with the problem to find out which combinations of heart rate p_i and systolic blood pressure b_i can lead to bad feeling. To this end, the doctors measured these parameters for n patients and asked them about their feeling. So, they obtained a sample with two features, that is divided into two classes c_i: «1» stands for bad feeling, and «0» denotes feeling well.

The data have been given to the polyclinic information center. Then the problem is to find an optimal separating boundary between classes such that AUC-ROC-metric be as large as possible.

It is required to draw a line through two points from the sample so that when predicting “1” on one side of the line or on the line itself and “0” in other cases, the classification is the best.

AUC is calculated as follows. The number of real ones K₁ and real zeros K₀ which are located on the positive half-plane are calculated. Then AUC = 0.5 + 0.5 ⋅ K₁N₁ − 0.5 ⋅ K₀N₀, where N₁ is the total number of ones, N₀ is the total number of zeros.

It is worth noting that we call positive (corresponding to the class «1») the half-plane for which AUC is greater.

Input format

The first line contains a single integer n. This is followed by n triples of the numbers p_i, b_i, c_i. The numbers p_i, b_i are real, c_i are 0 or 1. It is guaranteed that there is at least one point belonging to class 1 and at least one point belonging to class 0. There are no three points (p_i, b_i) at same line.

Output format

Output a single real number — maximal value of AUC metric with at least 3 digits after decimal point.

Constraints

2 ≤ n ≤ 1000 0 ≤ p_i, b_i ≤ 10⁹ c_i ∈ 0, 1

Sample tests

4
0.0 0.0 1
1.0 1.0 1
0.0 1.0 0
1.0 0.0 0

0.75

5
1 1 1
0 1 1
1 0 1
0 0 1
3 2 0

1

Problem D. Discarding numbers ≡

Statement

Vasya wrote down all the numbers from 1 to N in a row.

He performs the following algorithm until there are no more numbers.

1) Discards the number from the beginning of the list.

2) Discards the number from the end of the list.

3) Reverses the order of the remaining numbers.

4) Goes to the first instruction.

What number will Vasya discard on the K-th step?

Input format

First line contains 2 integers: N and K.

Output format

A single integer representing K-th discarded number.

Constraints

1 ≤ N ≤ 10⁹

1 ≤ K ≤ N

Notes on samples

Initial list: 1 2 3 4 5 6 7 8 9 10.

Vasya discards the first number: 2 3 4 5 6 7 8 9 10.

Discards from the end: 2 3 4 5 6 7 8 9.

Reverses the list: 9 8 7 6 5 4 3 2.

Discards the first number: 8 7 6 5 4 3 2.

Discards from the end: 8 7 6 5 4 3.

Reverses the list: 3 4 5 6 7 8.

The fifth discarded number was 3, which is the answer.

Sample tests

10 5

3

Problem E. Explorer kit ≡

Statement

Risorius is playing his favorite game, Doka 2, where a new event, "Fallen Crown," has been added. The event is represented as a sequence of n consecutive transitions. When at checkpoint i, Risorius can only transition to checkpoint i + 1. To move from checkpoint i to checkpoint i + 1, three tokens t_i1, t_i2, t_i3 must be collected. After transitioning from one checkpoint to the next, all accumulated tokens are lost.

The game includes h heroes, and for defeating the j-th hero, tokens t_j1, t_j2, t_j3 are awarded. The probability of Risorius winning against the k-th hero is p_k. Additionally, if the player loses against a particular hero 10 times consecutively while staying on the same checkpoint, they are awarded all three tokens regardless of the outcome.

The event starts at checkpoint 0 and ends upon reaching checkpoint n. Find the expected number of matches Risorius must play to complete the event, assuming optimal strategy.

Input format

The first line contains a single integer n. The next n lines each contain three integers t_i1, t_i2, t_i3 (for each checkpoint). The following line contains a single integer h. The next h lines each contain four integers t_j1, t_j2, t_j3, and p_j (for each hero, where p_j represents the win probability). It is guaranteed that a solution always exists.

Output format

Output a single floating-point number with two decimal places, representing the expected value of the number of matches required.

Constraints

1 ≤ n, h ≤ 100000 1 ≤ t_i1, t_i2, t_i3, t_j1, t_j2, t_j3 ≤ 10⁹ 0 ≤ p_j ≤ 100

Sample tests

3
1 2 3
1 1 1
3 4 5
5
1 2 2 50
1 3 4 25
5 1 1 25
5 5 5 100
6 7 8 100

16.32

1
1 1 1
1
1 2 2 50

5.99

Problem F. Fast Breeding ≡

Statement

Risorius is engaged in flower breeding. In her collection, there are n types of plants, and she has an unlimited number of each type. Each plant is characterized by the color of its flower. The color of the i-th plant is encoded by 3 numbers in the range from 1 to 64: (r_i, g_i, b_i).

When two types of plants with colors (r_a, g_a, b_a) and (r_b, g_b, b_b) are crossbred, the color of the new flower is calculated as follows: (⌊r_a + r_b2⌋, ⌊g_a + g_b2⌋, ⌊b_a + b_b2⌋). Furthermore, one of the plants involved in the crossbreeding must always be from the initial set of n plant types, otherwise, the result will be non-viable.

Risorius has received an order for a plant with the color (r, g, b). What is the minimum number of crossbreeding operations needed to obtain the desired plant color?

Input format

The first line contains three integers (r, g, b), which represent the desired flower color. The second line contains one integer n, representing the number of initial plant types. The next n lines each contain three integers r_i, g_i, b_i, representing the color of the i-th plant in the initial set.

Output format

Output −1 if it is impossible to obtain a plant with the desired color. Otherwise, output the minimum number of crossbreeding operations needed to obtain the desired plant.

Constraints

1 ≤ n ≤ 100

1 ≤ r, g, b, r_i, g_i, b_i ≤ 64

Sample tests

32 32 32
2
1 1 1
64 64 64 

1

64 64 64
2
1 1 1
63 63 63 

-1

Problem G. Gray, black and white squares ≡

Statement

Timofey has two semi-transparent films with a gray-and-white checkered pattern, each of size n × n. The first film has a cell size of 1 × 1, and the second film has a cell size of a × a. Both films start with a gray square in the top-left corner.

Today, Timofey placed the two films on top of each other. As a result:

Where gray squares from both films overlapped, the color turned black.

Where gray squares overlapped with white squares, the color remained gray.

Where white squares overlapped with white squares, the color remained white.

Your task is to determine how many single-unit squares of black, gray, and white color there are in total.

Input format

The input consists of two natural numbers, a and n.

Output format

The output should be three natural numbers — the number of black, gray, and white unit squares.

Constraints

2 ≤ a < n ≤ 10⁹

Example explanation

See the diagram for an example of tiling.

Sample tests

3
10

30
42
28

Problem H. Hidden tree ≡

Statement

This is an interactive problem. Your program will interact with a jury program by sending and receiving particular messages.

Petya has N vertices. He wants to connect them with edges to form a tree. Recall that a tree is a connected graph of N vertices and N − 1 edges.

Petya has already written a program that connects vertices with edges, but a problem arose during startup: the antivirus started complaining about it because of too much activity. To reduce the activity of his program, he asks you to write a second program, which will connect vertices in turn with his program.

And to make sure that the antivirus is less suspicious, Petya wants each node in the final tree to have no more than three edges.

Input format

The first line of input contains one integer N, the number of vertices in the tree.

Interaction protocol

To add an edge, your program should print "+ Ai Bi", where A_i, B_i — integers, the numbers of vertices to be connected by the edge.

The jury program will respond to your program with the line "ok". If after this it is still possible to add edges, then the jury program will also output "+ Ai Bi", where A_i, B_i — integers, the numbers of the vertices that are connected by an edge. It is guaranteed that the jury program adds edges according to all the described rules. After this, the turn again goes to your program.

When the tree has exactly N − 1 edges, your program should terminate.

If your program adds an unnecessary edge, it will receive "Wrong answer" verdict.

If your program makes incorrect query, it will receive "Presentation error" verdict.

If your program receives the string "error" instead of "ok" from the jury's program, it must immediately terminate. This is possible if your program violates the interaction protocol. If your program does not terminate, the verdict may differ from those described above (for example, it may be "Runtime error").

Every query must be a single line ending with single end-of-line (\n). Output buffers must be flushed after every line:

Constraints

3 ≤ N ≤ 1000

1 ≤ A_i, B_i ≤ N

Sample tests

6

ok
+ 5 6

ok
+ 1 6

ok

+ 1 2


+ 1 3


+ 2 4

3

ok
+ 2 3

+ 1 2

Problem I. Item enhancement ≡

Statement

Petya likes to play MMORPG and wants to beat everyone in PvP.

He just bought a cool weapon and wants to enhance it.

Initially enhancement level of the weapon is zero.

Petya has N enhancement stones of different levels in his inventory.

To raise enhancement level by 1, you need K stones of a higher level than the current level of the weapon, after this operation the stones disappear.

It is also possible to create a stone of one level higher from M stones of the same level.

What is the maximum enhancement level of the weapon Petya can reach?

Input format

First line contains 3 integers: N, K and M.

N - number of enhancement stones.

K - number of stones to raise enhancement level of the weapon by 1.

M - number of stones to craft a stone of a level higher by 1.

Second line contains an array A from N integers - levels of enhancement stones.

Output format

One integer - maximum enhancement level of the weapon that Petya can reach.

Constraints

1 ≤ N ≤ 10⁵

1 ≤ K ≤ 10⁹

1 ≤ M ≤ 10⁹

1 ≤ A_i ≤ 10⁹

Notes on samples

1-st: Petya crafts 3 stones of level 3 and uses it in any order.

2-nd: uses stones in order 2, 3, 4, 5.

3-rd: uses 2 stones of level 1, crafts stone of level 2 and uses 2 stones of level 2.

4-th: uses 1 stone of level 1.

5-th: uses two stones one time.

Sample tests

3 1 1
1 1 1

3

4 1 1
5 2 4 3

4

5 2 2
1 1 1 1 2

2

2 1 100
1 1

1

2 2 100
1 3

1

Problem J. Just pizza ≡

Statement

Elephant Pakhom is making a pizza, and he has exactly one pizza base, which is circular. For the toppings, he has n ingredients, each characterized by a number c_i, indicating the sector of the pizza that can be covered by that ingredient (with 360 meaning it is sufficient for exactly one layer). To make the pizza tasty, the following conditions must be met:

• Each point on the pizza must have the same number of topping layers.
• Two consecutive layers of the same ingredient are not allowed.
• All ingredients must be used entirely.
• Within a layer, the topping can be of different types.

Can Pakhom make a tasty pizza?

Input format

The first line contains a single integer n. The next n lines contain integers c_i.

Output format

Output YES if it is possible to make a tasty pizza; otherwise, output NO.

Constraints

1 ≤ n ≤ 100000 1 ≤ c_i ≤ 10⁹

Sample tests

3
360
720
720

YES

4
90
45
45
180

YES

5
180
180
180
180
180

NO

3
1080
180
180

NO

Problem K. Kolya writes a feature ≡

Statement

Kolya’s team switched to a new tool for automating continuous integration and continuous delivery processes - GitClub CI/CD.

Pipeline consists of N stages, and stages consist of M_i jobs.

All jobs in one stage are executed in parallel, and the next stage cannot begin until all jobs in the previous stage have completed.

Kolya needs to write a feature that, based on a given description of stages and durations of tasks, calculates total execution time of the pipeline.

Input format

First line contains one integer N - number of stages.

Next lines are descriptions of N stages, the description of each stage consists of three lines:

First line - string from small Latin letters and underscores X_i - name of the stage.

Second line - integer M_i - number of tasks in the stage.

Third line - integer array T_i - tasks durations in seconds.

Output format

One integer - total execution time of pipeline in seconds.

Constraints

1 ≤ N ≤ 100

1 ≤ |X_i| ≤ 100

1 ≤ M_i ≤ 1000

1 ≤ T_i,j ≤ 10⁷

Sample tests

3
build_stage
3
5 7 1
test_stage
5
1 6 8 9 2
deploy_stage
2
2 2

18

Problem L. Long sleep ≡

Statement

Natasha has c cats. One morning, when the cats woke up, they discovered that Natasha had beautifully arranged various objects on the table in a specific order. Naturally, the cats couldn’t resist and jumped onto the table, starting to knock down the objects one by one (starting from the first object).

For a cat to knock down an object with weight w_i, it takes w_i minutes. After that, the cat moves on to the next available object (in the order they are placed). The cats do not help each other (if one cat finishes earlier, it will simply watch the others knock down the remaining objects). Once all the objects have been moved, the cats will run to wake up Natasha and report their work.

Your task is to determine how long Natasha can keep sleeping.

Input format

The first two lines of input contain the natural numbers n and c. The third line contains n natural numbers w_i — the weights and order of the objects on the table.

Output format

Output a single natural number — the answer to the problem.

Constraints

1 ≤ c ≤ n ≤ 10⁵

1 ≤ w_i ≤ 10⁹

Example explanation

For example, on the table there are five objects with weights 1, 2, 3, 4, and 5, and three cats. The events will unfold as follows:

0 minutes: the cats begin their work: the first cat will knock down the first object weighing 1, the second cat will knock down the second object weighing 2, and the third cat will knock down the third object weighing 3.

1 minute: the first cat has knocked down the object weighing 1 and moves to knock down the object weighing 4.

2 minutes: the second cat has knocked down the object weighing 2 and moves to knock down the object weighing 5.

3 minutes: the third cat has knocked down the object weighing 3 and moves into observation mode, watching the others finish.

5 minutes: the first cat knocks down the object weighing 4 and also starts observing.

7 minutes: the second cat knocks down the object weighing 5. All objects have fallen, and the cats run to wake up Natasha.

Sample tests

5
3
1 2 3 4 5

7

Problem M. Match Schedule ≡

Statement

There are n teams participating in a football tournament. Each team plays against every other team exactly once. The goal is to arrange the matches such that, for each team, the number of home matches differs from the number of away matches by no more than 1.

You are required to output the schedule in the form of an n × n table. The i-th row should describe the matches of the i-th team, where:

• If the j-th element in the row is 'H', it means the match between teams i and j will take place at the home stadium of team i.
• If the j-th element in the row is 'A', it means the match will take place at the home stadium of team j.
• The diagonal elements (where i = j) should be marked with 'X' as no team plays against itself.

Input format

The first line of input contains a single integer n, representing the number of teams.

Output format

Output n lines, each containing n characters ('H', 'A', or 'X'), describing the desired match schedule. The match schedule must be consistent, meaning there are no contradictions.

Constraints

1 ≤ n ≤ 100

Sample tests

5

XAAHH
HXAAH
HHXAA
AHHXA
AAHHX

2

XA
HX