1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
White, Black and White Again
Contest: Testing Round 6
Difficulty rating: 2100
Tags: combinatorics, number theory

Polycarpus is sure that his life fits the description: "first there is a white stripe, then a black one, then a white one again". So, Polycarpus is sure that this rule is going to fulfill during the next n days. Polycarpus knows that he is in for w good events and b not-so-good events. At least one event is going to take place during each day. As each day is unequivocally characterizes as a part of a white or a black stripe, then each day is going to have events of the same type only (ether good or not-so-good).

What is the number of distinct ways this scenario can develop over the next n days if Polycarpus is in for a white stripe (a stripe that has good events only, the stripe's length is at least 1 day), the a black stripe (a stripe that has not-so-good events only, the stripe's length is at least 1 day) and a white stripe again (a stripe that has good events only, the stripe's length is at least 1 day). Each of n days will belong to one of the three stripes only.

Note that even the events of the same type are distinct from each other. Even if some events occur on the same day, they go in some order (there are no simultaneous events).

Write a code that prints the number of possible configurations to sort the events into days. See the samples for clarifications on which scenarios should be considered distinct. Print the answer modulo 1000000009 (109 + 9).

Input format:
The single line of the input contains integers n, w and b (3 ≤ n ≤ 4000, 2 ≤ w ≤ 4000, 1 ≤ b ≤ 4000) — the number of days, the number of good events and the number of not-so-good events. It is guaranteed that w + b ≥ n.

Output format:
Print the required number of ways modulo 1000000009 (109 + 9).

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
We'll represent the good events by numbers starting from 1 and the not-so-good events — by letters starting from 'a'. Vertical lines separate days.

In the first sample the possible ways are: "1|a|2" and "2|a|1". In the second sample the possible ways are: "1|a|b|2", "2|a|b|1", "1|b|a|2" and "2|b|a|1". In the third sample the possible ways are: "1|ab|2", "2|ab|1", "1|ba|2" and "2|ba|1".

Example input:
3 2 1

Example output:
2

Example input:
4 2 2

Example output:
4

Editorial:
Polygon
Contest: Testing Round 6
Difficulty rating: 2300
Tags: constructive algorithms, geometry

Polycarpus loves convex polygons, especially if all their angles are the same and all their sides are different. Draw for him any such polygon with the given number of vertexes.

Input format:
The input contains a single integer n (3 ≤ n ≤ 100) — the number of the polygon vertexes.

Output format:
Print n lines, containing the coordinates of the vertexes of the n-gon "xi yi" in the counter clockwise order. The coordinates of the vertexes shouldn't exceed 106 in their absolute value. The side lengths should fit within limits [1, 1000] (not necessarily integer). Mutual comparing sides and angles of your polygon during the test will go with precision of 10 - 3.

If there is no solution, print "No solution" (without the quotes).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
8

Example output:
1.000 0.000
7.000 0.000
9.000 2.000
9.000 3.000
5.000 7.000
3.000 7.000
0.000 4.000
0.000 1.000

Editorial:
Rollbacks (Easy Version)
Contest: Codeforces Round 893 (Div. 2)
Difficulty rating: 2500
Tags: brute force, data structures, dfs and similar, trees

This is an easy version of this problem. The only difference between the versions is that you have to solve the hard version in online mode. You can make hacks only if both versions of the problem are solved.

You have an array $$$a$$$, which is initially empty. You need to process queries of the following types:

- + $$$x$$$ — add the integer $$$x$$$ to the end of the array $$$a$$$.
- - $$$k$$$ — remove the last $$$k$$$ numbers from the array $$$a$$$.
- ! — roll back the last active change (i.e., make the array $$$a$$$ the way it was before the change). In this problem, only queries of the first two types (+ and -) are considered as changes.
- ? — find the number of distinct numbers in the array $$$a$$$.

Input format:
The first line contains an integer $$$q$$$ ($$$1 \leq q \leq 10^6$$$) — the number of queries.

The next $$$q$$$ lines contain the queries as described above.

It is guaranteed that

- in the queries of the first type, $$$1 \le x \le 10^6$$$;
- in the queries of the second type, $$$k \ge 1$$$ and $$$k$$$ does not exceed the current length of the array $$$a$$$;
- at the moment of the queries of the third type, there is at least one query of the first or of the second type that can be rolled back.

It is also guaranteed that the number of queries of the fourth type (?) does not exceed $$$10^5$$$.

Output format:
For each query of the fourth type output one integer — the number of distinct elements in array $$$a$$$ at the moment of query.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first example array $$$a$$$ changes as follows:

1. After the first query, $$$a=[1]$$$.
2. After the second query, $$$a=[1,2]$$$.
3. After the third query, $$$a=[1,2,2]$$$.
4. At the moment of the fourth query, there are $$$2$$$ distinct intergers in the array $$$a$$$: $$$1$$$ and $$$2$$$.
5. After the fifth query, $$$a=[1,2]$$$ (rolled back the change + 2).
6. After the sixth query, $$$a=[1,2,3]$$$.
7. After the seventh query, $$$a=[1]$$$.
8. At the moment of the eigth query, there is only one $$$1$$$ in the array $$$a$$$.
9. After the ninth query, $$$a=[1,1]$$$.
10. At the moment of the tenth query, there are only two $$$1$$$ in the array $$$a$$$.

In the second example array $$$a$$$ changes as follows:

1. After the first query, $$$a=[1]$$$.
2. After the second query, $$$a=[1,1\,000\,000]$$$.
3. At the moment of the third query, there are $$$2$$$ distinct intergers in the array $$$a$$$: $$$1$$$ and $$$1\,000\,000$$$.
4. After the fourth query, $$$a=[1]$$$ (rolled back the change + 1000000).
5. After the fifth query, $$$a=[]$$$ (rolled back the change + 1).
6. At the moment of the sixth query, there are no integers in the array $$$a$$$, so the answer to this query is $$$0$$$.

Example input:
10
+ 1
+ 2
+ 2
?
!
+ 3
- 2
?
+ 1
?

Example output:
2
1
1

Example input:
6
+ 1
+ 1000000
?
!
!
?

Example output:
2
0

Editorial:
One and Two
Contest: Codeforces Round 851 (Div. 2)
Difficulty rating: 800
Tags: brute force, implementation, math

You are given a sequence $$$a_1, a_2, \ldots, a_n$$$. Each element of $$$a$$$ is $$$1$$$ or $$$2$$$.

Find out if an integer $$$k$$$ exists so that the following conditions are met.

- $$$1 \leq k \leq n-1$$$, and
- $$$a_1 \cdot a_2 \cdot \ldots \cdot a_k = a_{k+1} \cdot a_{k+2} \cdot \ldots \cdot a_n$$$.

If there exist multiple $$$k$$$ that satisfy the given condition, print the smallest.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). Description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$2 \leq n \leq 1000$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 2$$$).

Output format:
For each test case, if there is no such $$$k$$$, print $$$-1$$$.

Otherwise, print the smallest possible $$$k$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For the first test case, $$$k=2$$$ satisfies the condition since $$$a_1 \cdot a_2 = a_3 \cdot a_4 \cdot a_5 \cdot a_6 = 4$$$. $$$k=3$$$ also satisfies the given condition, but the smallest should be printed.

For the second test case, there is no $$$k$$$ that satisfies $$$a_1 \cdot a_2 \cdot \ldots \cdot a_k = a_{k+1} \cdot a_{k+2} \cdot \ldots \cdot a_n$$$

For the third test case, $$$k=1$$$, $$$2$$$, and $$$3$$$ satisfy the given condition, so the answer is $$$1$$$.

Example input:
3
6
2 2 1 2 1 2
3
1 2 1
4
1 1 1 1

Example output:
2
-1
1

Editorial:
There should be same number of $$$2$$$ at $$$a_1, a_2, \cdots a_k$$$ and $$$a_{k+1}, \cdots, a_n$$$.
By checking every $$$k$$$, we can solve the problem at $$$O(N^2)$$$. By sweeping $$$k$$$ from $$$1$$$ to $$$n-1$$$, we can solve the problem in $$$O(N)$$$. Not counting the number of $$$2$$$ but naively multiplying using sweeping in python was accepted since it has time complexity $$$O(N^2)$$$.
Checking every $$$k$$$ and naively multiplying solutions are $$$O(N^3)$$$, so those solutions won't fit in time limit.
Sum of Two Numbers
Contest: Codeforces Round 851 (Div. 2)
Difficulty rating: 1100
Tags: constructive algorithms, greedy, implementation, math, probabilities

The sum of digits of a non-negative integer $$$a$$$ is the result of summing up its digits together when written in the decimal system. For example, the sum of digits of $$$123$$$ is $$$6$$$ and the sum of digits of $$$10$$$ is $$$1$$$. In a formal way, the sum of digits of $$$\displaystyle a=\sum_{i=0}^{\infty} a_i \cdot 10^i$$$, where $$$0 \leq a_i \leq 9$$$, is defined as $$$\displaystyle\sum_{i=0}^{\infty}{a_i}$$$.

Given an integer $$$n$$$, find two non-negative integers $$$x$$$ and $$$y$$$ which satisfy the following conditions.

- $$$x+y=n$$$, and
- the sum of digits of $$$x$$$ and the sum of digits of $$$y$$$ differ by at most $$$1$$$.

It can be shown that such $$$x$$$ and $$$y$$$ always exist.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10\,000$$$).

Each test case consists of a single integer $$$n$$$ ($$$1 \leq n \leq 10^9$$$)

Output format:
For each test case, print two integers $$$x$$$ and $$$y$$$.

If there are multiple answers, print any.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the second test case, the sum of digits of $$$67$$$ and the sum of digits of $$$94$$$ are both $$$13$$$.

In the third test case, the sum of digits of $$$60$$$ is $$$6$$$, and the sum of digits of $$$7$$$ is $$$7$$$.

Example input:
5
1
161
67
1206
19

Example output:
1 0
67 94
60 7
1138 68
14 5

Editorial:
Let's assume that there is no carry while adding $$$x$$$ and $$$y$$$. Denote $$$n=a_9 \cdots a_1a_0$$$, $$$x=b_9 \cdots b_1b_0$$$, $$$y=c_9 \cdots c_1c_0$$$ in decimal system. The condition can be changed as the following condition.
- $$$a_i=b_i+c_i$$$ for all $$$0 \leq i \leq 9$$$. - Sum of $$$b_i$$$ and sum of $$$c_i$$$ should differ by at most $$$1$$$.
If $$$a_i$$$ is even, let $$$b_i=c_i=a_i/2$$$. Otherwise, let $$$b_i$$$ and $$$c_i$$$ be $$$\frac{a_i+1}{2}$$$ or $$$\frac{a_i-1}{2}$$$. By alternating between $$$(b_i, c_i)=(\frac{a_i+1}{2}, \frac{a_i-1}{2})$$$ and $$$(b_i, c_i)=(\frac{a_i-1}{2}, \frac{a_i+1}{2})$$$, we can satisfy the condition where sum of $$$b_i$$$ and sum of $$$c_i$$$ differ by at most $$$1$$$.
There is an alternative solution. If $$$n$$$ is even, divide it into ($$$\frac{n}{2}, \frac{n}{2}$$$). If remainder of $$$n$$$ divided by $$$10$$$ is not $$$9$$$, divide it into ($$$\frac{n+1}{2}, \frac{n-1}{2}$$$). If remainder of $$$n$$$ divided by $$$10$$$ is $$$9$$$, recursively find an answer for $$$\lfloor \frac{n}{10} \rfloor$$$ which is ($$$x', y'$$$) and the answer will be ($$$10x'+4, 10y'+5$$$) or ($$$10x'+5, 10y'+4$$$) depending on what number has a bigger sum of digits.
The following solution has a countertest.
1. Trying to find $$$x$$$ and $$$y$$$ by bruteforce from ($$$1, n-1$$$). 2. Trying to find $$$x$$$ and $$$y$$$ by bruteforce from ($$$\frac{n+1}{2}, \frac{n-1}{2}$$$)
A solution that randomly finds ($$$x, y$$$) passes.
Matching Numbers
Contest: Codeforces Round 851 (Div. 2)
Difficulty rating: 1300
Tags: constructive algorithms, greedy, math

You are given an integer $$$n$$$. Pair the integers $$$1$$$ to $$$2n$$$ (i.e. each integer should be in exactly one pair) so that each sum of matched pairs is consecutive and distinct.

Formally, let $$$(a_i, b_i)$$$ be the pairs that you matched. $$$\{a_1, b_1, a_2, b_2, \ldots, a_n, b_n\}$$$ should be a permutation of $$$\{1, 2, \ldots, 2n\}$$$. Let the sorted list of $$$\{a_1+b_1, a_2+b_2, \ldots, a_n+b_n\}$$$ be $$$s_1 < s_2 < \ldots < s_n$$$. We must have $$$s_{i+1}-s_i = 1$$$ for $$$1 \le i \le n - 1$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

For each test case, a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) is given.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

Output format:
For each test case, if it is impossible to make such a pairing, print "No".

Otherwise, print "Yes" followed by $$$n$$$ lines.

At each line, print two integers that are paired.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

If there are multiple solutions, print any.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For the third test case, each integer from $$$1$$$ to $$$6$$$ appears once. The sums of matched pairs are $$$4+2=6$$$, $$$1+6=7$$$, and $$$3+5=8$$$, which are consecutive and distinct.

Example input:
4
1
2
3
4

Example output:
Yes
1 2
No
Yes
1 6
3 5
4 2
No

Editorial:
Let's assume that $$$1$$$ to $$$2n$$$ is paired and each sum of pair is $$$k, k+1, \cdots, k+n-1$$$. Sum from $$$1$$$ to $$$2n$$$ should equal to the sum of $$$k$$$ to $$$k+n-1$$$. So we obtain $$$n(2n+1)=\frac{(2k+n-1)n}{2}$$$, which leads to $$$4n+2=2k+n-1$$$. Since $$$4n+2$$$ is even, $$$2k+n-1$$$ should be even. So if $$$n$$$ is even, we cannot find such pairing.
If $$$n$$$ is odd, there are various ways to make such pairing. Let $$$m=\frac{n-1}{2}$$$. $$$(1, 3m+3), (2, 3m+4), \ldots (m, 4m+2), (m+1, 2m+2), (m+2, 2m+3), \ldots (2m+1, 3m+2)$$$ can be such pairing.
Plant
Contest: Codeforces Round 118 (Div. 1)
Difficulty rating: 1300
Tags: math

Dwarfs have planted a very interesting plant, which is a triangle directed "upwards". This plant has an amusing feature. After one year a triangle plant directed "upwards" divides into four triangle plants: three of them will point "upwards" and one will point "downwards". After another year, each triangle plant divides into four triangle plants: three of them will be directed in the same direction as the parent plant, and one of them will be directed in the opposite direction. Then each year the process repeats. The figure below illustrates this process.

Help the dwarfs find out how many triangle plants that point "upwards" will be in n years.

Input format:
The first line contains a single integer n (0 ≤ n ≤ 1018) — the number of full years when the plant grew.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

Output format:
Print a single integer — the remainder of dividing the number of plants that will point "upwards" in n years by 1000000007 (109 + 7).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The first test sample corresponds to the second triangle on the figure in the statement. The second test sample corresponds to the third one.

Example input:
1

Example output:
3

Example input:
2

Example output:
10

Editorial:
Mushroom Scientists
Contest: Codeforces Round 118 (Div. 1)
Difficulty rating: 1800
Tags: math, ternary search

As you very well know, the whole Universe traditionally uses three-dimensional Cartesian system of coordinates. In this system each point corresponds to three real coordinates (x, y, z). In this coordinate system, the distance between the center of the Universe and the point is calculated by the following formula: $$\sqrt{x^2 + y^2 + z^2}$$. Mushroom scientists that work for the Great Mushroom King think that the Universe isn't exactly right and the distance from the center of the Universe to a point equals xa·yb·zc.

To test the metric of mushroom scientists, the usual scientists offered them a task: find such x, y, z (0 ≤ x, y, z; x + y + z ≤ S), that the distance between the center of the Universe and the point (x, y, z) is maximum possible in the metric of mushroom scientists. The mushroom scientists aren't good at maths, so they commissioned you to do the task.

Note that in this problem, it is considered that 00 = 1.

Input format:
The first line contains a single integer S (1 ≤ S ≤ 103) — the maximum sum of coordinates of the sought point.

The second line contains three space-separated integers a, b, c (0 ≤ a, b, c ≤ 103) — the numbers that describe the metric of mushroom scientists.

Output format:
Print three real numbers — the coordinates of the point that reaches maximum value in the metrics of mushroom scientists. If there are multiple answers, print any of them that meets the limitations.

A natural logarithm of distance from the center of the Universe to the given point in the metric of mushroom scientists shouldn't differ from the natural logarithm of the maximum distance by more than 10 - 6. We think that ln(0) =  - ∞.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3
1 1 1

Example output:
1.0 1.0 1.0

Example input:
3
2 0 0

Example output:
3.0 0.0 0.0

Editorial:
Clever Fat Rat
Contest: Codeforces Round 118 (Div. 1)
Difficulty rating: 2500
Tags: dp

The Fat Rat and his friend Сerealguy have had a bet whether at least a few oats are going to descend to them by some clever construction. The figure below shows the clever construction.

A more formal description of the clever construction is as follows. The clever construction consists of n rows with scales. The first row has n scales, the second row has (n - 1) scales, the i-th row has (n - i + 1) scales, the last row has exactly one scale. Let's number the scales in each row from the left to the right, starting from 1. Then the value of wi, k in kilograms (1 ≤ i ≤ n; 1 ≤ k ≤ n - i + 1) is the weight capacity parameter of the k-th scale in the i-th row.

If a body whose mass is not less than wi, k falls on the scale with weight capacity wi, k, then the scale breaks. At that anything that the scale has on it, either falls one level down to the left (if possible) or one level down to the right (if possible). In other words, if the scale wi, k (i < n) breaks, then there are at most two possible variants in which the contents of the scale's pan can fall out: all contents of scale wi, k falls either on scale wi + 1, k - 1 (if it exists), or on scale wi + 1, k (if it exists). If scale wn, 1 breaks, then all its contents falls right in the Fat Rat's claws. Please note that the scales that are the first and the last in a row, have only one variant of dropping the contents.

Initially, oats are simultaneously put on all scales of the first level. The i-th scale has ai kilograms of oats put on it. After that the scales start breaking and the oats start falling down in some way. You can consider everything to happen instantly. That is, the scale breaks instantly and the oats also fall instantly.

The Fat Rat is sure that whatever happens, he will not get the oats from the first level. Cerealguy is sure that there is such a scenario, when the rat gets at least some number of the oats. Help the Fat Rat and the Cerealguy. Determine, which one is right.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 50) — the number of rows with scales.

The next line contains n space-separated integers ai (1 ≤ ai ≤ 106) — the masses of the oats in kilograms.

The next n lines contain descriptions of the scales: the i-th line contains (n - i + 1) space-separated integers wi, k (1 ≤ wi, k ≤ 106) — the weight capacity parameters for the scales that stand on the i-th row, in kilograms.

Output format:
Print "Fat Rat" if the Fat Rat is right, otherwise print "Cerealguy".

Constraints:
Time limit: 2.5 s
Memory limit: 256.0 MB

Note:
Notes to the examples:

- The first example: the scale with weight capacity 2 gets 1. That means that the lower scale don't break.
- The second sample: all scales in the top row obviously break. Then the oats fall on the lower row. Their total mass is 4,and that's exactly the weight that the lower scale can "nearly endure". So, as 4  ≥  4, the scale breaks.

Example input:
1
1
2

Example output:
Fat Rat

Example input:
2
2 2
1 2
4

Example output:
Cerealguy

Editorial:
Visit of the Great
Contest: Codeforces Round 118 (Div. 1)
Difficulty rating: 2600
Tags: math, number theory

The Great Mushroom King descended to the dwarves, but not everyone managed to see him. Only the few chosen ones could see the King.

We know that only LCM(k2l + 1, k2l + 1 + 1, ..., k2r + 1) dwarves can see the Great Mushroom King. Numbers k, l, r are chosen by the Great Mushroom King himself in some complicated manner which is unclear to common dwarves.

The dwarven historians decided to document all visits of the Great Mushroom King. For each visit the dwarven historians know three integers ki, li, ri, chosen by the Great Mushroom King for this visit. They also know a prime number pi. Help them to count the remainder of dividing the number of dwarves who can see the King, by number pi, for each visit.

Input format:
The first line contains the single integer t (1 ≤ t ≤ 105) — the number of the King's visits.

Each of the following t input lines contains four space-separated integers ki, li, ri and pi (1 ≤ ki ≤ 106; 0 ≤ li ≤ ri ≤ 1018; 2 ≤ pi ≤ 109) — the numbers, chosen by the Great Mushroom King and the prime module, correspondingly.

It is guaranteed that for all visits number pi is prime.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output format:
For each visit print the answer on a single line — the remainder of dividing the number of the dwarves who can see the King this time, by number pi. Print the answers for the visits in the order, in which the visits are described in the input.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
We consider that LCM(a1, a2, ..., an) represents the least common multiple of numbers a1, a2, ..., an.

We consider that x0 = 1, for any x.

Example input:
2
3 1 10 2
5 0 4 3

Example output:
0
0

Editorial: