1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Minimum Varied Number
Contest: Codeforces Round 811 (Div. 3)
Difficulty rating: 800
Tags: greedy

Find the minimum number with the given sum of digits $$$s$$$ such that all digits in it are distinct (i.e. all digits are unique).

For example, if $$$s=20$$$, then the answer is $$$389$$$. This is the minimum number in which all digits are different and the sum of the digits is $$$20$$$ ($$$3+8+9=20$$$).

For the given $$$s$$$ print the required number.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 45$$$) — the number of test cases.

Each test case is specified by a line that contains the only integer $$$s$$$ ($$$1 \le s \le 45$$$).

Output format:
Print $$$t$$$ integers — the answers to the given test cases.

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

Example input:
4
20
8
45
10

Example output:
389
8
123456789
19

Editorial:
Let's use the greedy solution: we will go through the digits in decreasing order. If the sum of $$$s$$$ we need to dial is greater than the current digit, we add the current digit to the end of the line with the answer.
Note that in this way we will always get an answer consisting of the minimum possible number of digits, because we are going through the digits in descending order.
Suppose that the resulting number is not optimal. Then some digit can be reduced, and some digit that comes after it can be increased, in order to save the sum (we can not increase the digit before it, as then we get a number greater than the current one). Two variants are possible.
• We want to increase the digit $$$x$$$ to $$$x+1$$$, but then it becomes equal to the digit following it, or exceeds the value $$$9$$$. Then we can't increment that digit.
• Otherwise, in the first step, we can get $$$x+1$$$ instead of $$$x$$$, but since we are going through the digits in decreasing order, we cannot get the value of $$$x$$$ in that case. Contradiction.
Build a Tree and That Is It
Contest: Codeforces Round 811 (Div. 3)
Difficulty rating: 1900
Tags: constructive algorithms, implementation, trees

A tree is a connected undirected graph without cycles. Note that in this problem, we are talking about not rooted trees.

You are given four positive integers $$$n, d_{12}, d_{23}$$$ and $$$d_{31}$$$. Construct a tree such that:

- it contains $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$,
- the distance (length of the shortest path) from vertex $$$1$$$ to vertex $$$2$$$ is $$$d_{12}$$$,
- distance from vertex $$$2$$$ to vertex $$$3$$$ is $$$d_{23}$$$,
- the distance from vertex $$$3$$$ to vertex $$$1$$$ is $$$d_{31}$$$.

Output any tree that satisfies all the requirements above, or determine that no such tree exists.

Input format:
The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) —the number of test cases in the test.

This is followed by $$$t$$$ test cases, each written on a separate line.

Each test case consists of four positive integers $$$n, d_{12}, d_{23}$$$ and $$$d_{31}$$$ ($$$3 \le n \le 2\cdot10^5; 1 \le d_{12}, d_{23}, d_{31} \le n-1$$$).

It is guaranteed that the sum of $$$n$$$ values for all test cases does not exceed $$$2\cdot10^5$$$.

Output format:
For each test case, print YES if the suitable tree exists, and NO otherwise.

If the answer is positive, print another $$$n-1$$$ line each containing a description of an edge of the tree — a pair of positive integers $$$x_i, y_i$$$, which means that the $$$i$$$th edge connects vertices $$$x_i$$$ and $$$y_i$$$.

The edges and vertices of the edges can be printed in any order. If there are several suitable trees, output any of them.

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

Example input:
9
5 1 2 1
5 2 2 2
5 2 2 3
5 2 2 4
5 3 2 3
4 2 1 1
4 3 1 1
4 1 2 3
7 1 4 1

Example output:
YES
1 2
4 1
3 1
2 5
YES
4 3
2 5
1 5
5 3
NO
YES
2 4
4 1
2 5
5 3
YES
5 4
4 1
2 5
3 5
YES
2 3
3 4
1 3
NO
YES
4 3
1 2
2 4
NO

Editorial:
If the answer exists, you can hang the tree by some vertex such that the distances $$$d_{12}, d_{23}$$$ and $$$d_{31}$$$ can be expressed through the sums of distances to vertices $$$1,2$$$ and $$$3$$$. Then from the system of equations we express the required values of distances to vertices $$$1,2,3$$$ and construct a suitable tree. If the distance to a vertex is $$$0$$$, then that vertex is the root. There cannot be two roots, nor can there be negative distances.
If none of the vertices of $$$1,2,3$$$ is the root, then make vertex $$$4$$$ the root.
Next we build the required tree: add the required number of unique vertices on the path from the root to vertices $$$1,2,3$$$. Note also that if the sum of distances is greater than or equal to $$$n$$$, then we cannot build the tree either.
The remaining vertices can be simply joined to the root.
Epic Game
Contest: Codeforces Beta Round 90
Difficulty rating: 800
Tags: implementation

Simon and Antisimon play a game. Initially each player receives one fixed positive integer that doesn't change throughout the game. Simon receives number a and Antisimon receives number b. They also have a heap of n stones. The players take turns to make a move and Simon starts. During a move a player should take from the heap the number of stones equal to the greatest common divisor of the fixed number he has received and the number of stones left in the heap. A player loses when he cannot take the required number of stones (i. e. the heap has strictly less stones left than one needs to take).

Your task is to determine by the given a, b and n who wins the game.

Input format:
The only string contains space-separated integers a, b and n (1 ≤ a, b, n ≤ 100) — the fixed numbers Simon and Antisimon have received correspondingly and the initial number of stones in the pile.

Output format:
If Simon wins, print "0" (without the quotes), otherwise print "1" (without the quotes).

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

Note:
The greatest common divisor of two non-negative integers a and b is such maximum positive integer k, that a is divisible by k without remainder and similarly, b is divisible by k without remainder. Let gcd(a, b) represent the operation of calculating the greatest common divisor of numbers a and b. Specifically, gcd(x, 0) = gcd(0, x) = x.

In the first sample the game will go like that:

- Simon should take gcd(3, 9) = 3 stones from the heap. After his move the heap has 6 stones left.
- Antisimon should take gcd(5, 6) = 1 stone from the heap. After his move the heap has 5 stones left.
- Simon should take gcd(3, 5) = 1 stone from the heap. After his move the heap has 4 stones left.
- Antisimon should take gcd(5, 4) = 1 stone from the heap. After his move the heap has 3 stones left.
- Simon should take gcd(3, 3) = 3 stones from the heap. After his move the heap has 0 stones left.
- Antisimon should take gcd(5, 0) = 5 stones from the heap. As 0 < 5, it is impossible and Antisimon loses.

In the second sample each player during each move takes one stone from the heap. As n is even, Antisimon takes the last stone and Simon can't make a move after that.

Example input:
3 5 9

Example output:
0

Example input:
1 1 100

Example output:
1

Editorial:
Education Reform
Contest: Codeforces Beta Round 90
Difficulty rating: 2000
Tags: dp

Yet another education system reform has been carried out in Berland recently. The innovations are as follows:

An academic year now consists of n days. Each day pupils study exactly one of m subjects, besides, each subject is studied for no more than one day. After the lessons of the i-th subject pupils get the home task that contains no less than ai and no more than bi exercises. Besides, each subject has a special attribute, the complexity (ci). A school can make its own timetable, considering the following conditions are satisfied:

- the timetable should contain the subjects in the order of the complexity's strict increasing;
- each day, except for the first one, the task should contain either k times more exercises, or more by k compared to the previous day (more formally: let's call the number of home task exercises in the i-th day as xi, then for each i (1 < i ≤ n): either xi = k + xi - 1 or xi = k·xi - 1 must be true);
- the total number of exercises in all home tasks should be maximal possible.

All limitations are separately set for each school.

It turned out that in many cases ai and bi reach 1016 (however, as the Berland Minister of Education is famous for his love to half-measures, the value of bi - ai doesn't exceed 100). That also happened in the Berland School №256. Nevertheless, you as the school's principal still have to work out the timetable for the next academic year...

Input format:
The first line contains three integers n, m, k (1 ≤ n ≤ m ≤ 50, 1 ≤ k ≤ 100) which represent the number of days in an academic year, the number of subjects and the k parameter correspondingly. Each of the following m lines contains the description of a subject as three integers ai, bi, ci (1 ≤ ai ≤ bi ≤ 1016, bi - ai ≤ 100, 1 ≤ ci ≤ 100) — two limitations to the number of exercises on the i-th subject and the complexity of the i-th subject, correspondingly. Distinct subjects can have the same complexity. The subjects are numbered with integers from 1 to m.

Please do not use the %lld specificator to read or write 64-bit numbers in С++. It is preferred to use the cin stream or the %I64d specificator.

Output format:
If no valid solution exists, print the single word "NO" (without the quotes). Otherwise, the first line should contain the word "YES" (without the quotes) and the next n lines should contain any timetable that satisfies all the conditions. The i + 1-th line should contain two positive integers: the number of the subject to study on the i-th day and the number of home task exercises given for this subject. The timetable should contain exactly n subjects.

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

Example input:
4 5 2
1 10 1
1 10 2
1 10 3
1 20 4
1 100 5

Example output:
YES
2 8
3 10
4 20
5 40

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

Example output:
NO

Editorial:
String Transformation
Contest: Codeforces Beta Round 90
Difficulty rating: 2500
Tags: hashing, strings

Let s be a string whose length equals n. Its characters are numbered from 0 to n - 1, i and j are integers, 0 ≤ i < j < n. Let's define function f as follows:

f(s, i, j) = s[i + 1... j - 1] + r(s[j... n - 1]) + r(s[0... i]).

Here s[p... q] is a substring of string s, that starts in position p and ends in position q (inclusive); "+" is the string concatenation operator; r(x) is a string resulting from writing the characters of the x string in the reverse order. If j = i + 1, then the substring s[i + 1... j - 1] is considered empty.

You are given two strings a and b. Find such values of i and j, that f(a, i, j) = b. Number i should be maximally possible. If for this i there exists several valid values of j, choose the minimal j.

Input format:
The first two input lines are non-empty strings a and b correspondingly. Each string's length does not exceed 106 characters. The strings can contain any characters with ASCII codes from 32 to 126 inclusive.

Output format:
Print two integers i, j — the answer to the problem. If no solution exists, print "-1 -1" (without the quotes).

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

Example input:
Die Polizei untersucht eine Straftat im IT-Bereich.
untersucht eine Straftat.hciereB-TI mi  ieziloP eiD

Example output:
11 36

Example input:
cbaaaa
aaaabc

Example output:
4 5

Editorial:
Alternative Reality
Contest: Codeforces Beta Round 90
Difficulty rating: 2400
Tags: geometry

In the year of 3000 travelling around parallel realities became a routine thing. However one has to take into consideration that travelling like that is highly dangerous as you never know beforehand where you're gonna get...

Little Vasya, for instance, found himself in a gaming reality and now he has to successfully complete all levels of a very weird game to get back. The gaming reality is a three-dimensional space where n points are given. The game has m levels and at the beginning of the i-th level the player is positioned at some plane Qi that passes through the origin. On each level Vasya has to use special robots to construct and activate n powerful energy spheres of the equal radius with centers at the given points. The player chooses the radius of the spheres himself. The player has to spend R units of money to construct spheres whose radius equals R (consequently, one can construct spheres whose radius equals zero for free). Besides, once for each level a player can choose any point in space and release a laser ray from there, perpendicular to plane Qi (this action costs nothing). The ray can either be directed towards the plane or from the plane. The spheres that share at least one point with the ray will be immediately activated. The level is considered completed if the player has managed to activate all spheres. Note that the centers of the spheres are the same for all m levels but the spheres do not remain: the player should construct them anew on each new level.

Help Vasya find out what minimum sum of money will be enough to complete each level.

Input format:
The first line contains two integers n and m (1 ≤ n ≤ 900, 1 ≤ m ≤ 100) — the number of energetic spheres and the number of levels in the game correspondingly.

Each of the following n lines contains three integers xi, yi, zi (0 ≤ xi, yi, zi ≤ 104) — the coordinates of the center of the i-th sphere. Assume that these points do not change their positions throughout the game.

Then follow m lines, each containing three integers ai, bi, ci (0 ≤ ai, bi, ci ≤ 100, ai2 + bi2 + ci2 > 0). These numbers are the coefficients in the equation of plane Qi (aix + biy + ciz = 0), where the player is positioned at the beginning of the i-th level.

Output format:
Print m numbers, one per line: the i-th line should contain the minimum sum of money needed to complete the i-th level. The absolute or relative error should not exceed 10 - 6.

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

Example input:
4 1
0 0 0
0 1 0
1 0 0
1 1 0
0 0 1

Example output:
0.7071067812

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

Example output:
1.6329931619
1.6366341768
1.5411035007

Editorial:
Shop
Contest: Codeforces Round 295 (Div. 1)
Difficulty rating: 2800
Tags: greedy

Vasya plays one very well-known and extremely popular MMORPG game. His game character has k skill; currently the i-th of them equals to ai. Also this game has a common rating table in which the participants are ranked according to the product of all the skills of a hero in the descending order.

Vasya decided to 'upgrade' his character via the game store. This store offers n possible ways to improve the hero's skills; Each of these ways belongs to one of three types:

1. assign the i-th skill to b;
2. add b to the i-th skill;
3. multiply the i-th skill by b.

Unfortunately, a) every improvement can only be used once; b) the money on Vasya's card is enough only to purchase not more than m of the n improvements. Help Vasya to reach the highest ranking in the game. To do this tell Vasya which of improvements he has to purchase and in what order he should use them to make his rating become as high as possible. If there are several ways to achieve it, print any of them.

Input format:
The first line contains three numbers — k, n, m (1 ≤ k ≤ 105, 0 ≤ m ≤ n ≤ 105) — the number of skills, the number of improvements on sale and the number of them Vasya can afford.

The second line contains k space-separated numbers ai (1 ≤ ai ≤ 106), the initial values of skills.

Next n lines contain 3 space-separated numbers tj, ij, bj (1 ≤ tj ≤ 3, 1 ≤ ij ≤ k, 1 ≤ bj ≤ 106) — the type of the j-th improvement (1 for assigning, 2 for adding, 3 for multiplying), the skill to which it can be applied and the value of b for this improvement.

Output format:
The first line should contain a number l (0 ≤ l ≤ m) — the number of improvements you should use.

The second line should contain l distinct space-separated numbers vi (1 ≤ vi ≤ n) — the indices of improvements in the order in which they should be applied. The improvements are numbered starting from 1, in the order in which they appear in the input.

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

Example input:
2 4 3
13 20
1 1 14
1 2 30
2 1 6
3 2 2

Example output:
3
2 3 4

Editorial:
Cycling City
Contest: Codeforces Round 295 (Div. 1)
Difficulty rating: 3100
Tags: dfs and similar, graphs

You are organizing a cycling race on the streets of the city. The city contains n junctions, some pairs of them are connected by roads; on each road you can move in any direction. No two roads connect the same pair of intersections, and no road connects the intersection with itself.

You want the race to be open to both professional athletes and beginner cyclists, and that's why you will organize the race in three nominations: easy, moderate and difficult; each participant will choose the more suitable nomination. For each nomination you must choose the route — the chain of junctions, consecutively connected by roads. Routes must meet the following conditions:

- all three routes should start at the same intersection, and finish at the same intersection (place of start and finish can't be the same);
- to avoid collisions, no two routes can have common junctions (except for the common start and finish), and can not go along the same road (irrespective of the driving direction on the road for those two routes);
- no route must pass twice through the same intersection or visit the same road twice (irrespective of the driving direction on the road for the first and second time of visit).

Preparing for the competition is about to begin, and you need to determine the routes of the race as quickly as possible. The length of the routes is not important, it is only important that all the given requirements were met.

Input format:
The first line contains two integers n and m (1 ≤ n, m ≤ 2·105) — the number of intersections and roads, respectively.

The following m lines contain two integers — the numbers of the intersections connected by a road (the intersections are numbered starting with 1). It is guaranteed that each pair of intersections is connected by no more than one road, and no road connects the intersection to itself.

Please note that it is not guaranteed that you can get from any junction to any other one by using the roads.

Output format:
If it is possible to create the routes, in the first line print "YES". In the next three lines print the descriptions of each of the three routes in the format "l p1 ... pl", where l is the number of intersections in the route, and p1, ..., pl are their numbers in the order they follow. The routes must meet all the requirements specified in the statement.

If it is impossible to make the routes in accordance with the requirements, print NO.

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

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

Example output:
NO

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

Example output:
YES
3 5 4 1
3 5 3 1
3 5 2 1

Editorial:
Circle of Students
Contest: Codeforces Round 579 (Div. 3)
Difficulty rating: 1000
Tags: implementation

There are $$$n$$$ students standing in a circle in some order. The index of the $$$i$$$-th student is $$$p_i$$$. It is guaranteed that all indices of students are distinct integers from $$$1$$$ to $$$n$$$ (i. e. they form a permutation).

Students want to start a round dance. A clockwise round dance can be started if the student $$$2$$$ comes right after the student $$$1$$$ in clockwise order (there are no students between them), the student $$$3$$$ comes right after the student $$$2$$$ in clockwise order, and so on, and the student $$$n$$$ comes right after the student $$$n - 1$$$ in clockwise order. A counterclockwise round dance is almost the same thing — the only difference is that the student $$$i$$$ should be right after the student $$$i - 1$$$ in counterclockwise order (this condition should be met for every $$$i$$$ from $$$2$$$ to $$$n$$$).

For example, if the indices of students listed in clockwise order are $$$[2, 3, 4, 5, 1]$$$, then they can start a clockwise round dance. If the students have indices $$$[3, 2, 1, 4]$$$ in clockwise order, then they can start a counterclockwise round dance.

Your task is to determine whether it is possible to start a round dance. Note that the students cannot change their positions before starting the dance; they cannot swap or leave the circle, and no other student can enter the circle.

You have to answer $$$q$$$ independent queries.

Input format:
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 200$$$) — the number of queries. Then $$$q$$$ queries follow.

The first line of the query contains one integer $$$n$$$ ($$$1 \le n \le 200$$$) — the number of students.

The second line of the query contains a permutation of indices $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$), where $$$p_i$$$ is the index of the $$$i$$$-th student (in clockwise order). It is guaranteed that all $$$p_i$$$ are distinct integers from $$$1$$$ to $$$n$$$ (i. e. they form a permutation).

Output format:
For each query, print the answer on it. If a round dance can be started with the given order of students, print "YES". Otherwise print "NO".

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

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

Example output:
YES
YES
NO
YES
YES

Editorial:
We just need to find the position of the $$$1$$$ in the array and then check if the sequence $$$2, 3, \dots, n$$$ is going counterclockwise or clockwise from the position $$$pos-1$$$ or $$$pos+1$$$ correspondingly. We can do this by two cycles.
Total complexity: $$$O(n)$$$.
Equal Rectangles
Contest: Codeforces Round 579 (Div. 3)
Difficulty rating: 1200
Tags: greedy, math

You are given $$$4n$$$ sticks, the length of the $$$i$$$-th stick is $$$a_i$$$.

You have to create $$$n$$$ rectangles, each rectangle will consist of exactly $$$4$$$ sticks from the given set. The rectangle consists of four sides, opposite sides should have equal length and all angles in it should be right. Note that each stick can be used in only one rectangle. Each stick should be used as a side, you cannot break the stick or use it not to the full length.

You want to all rectangles to have equal area. The area of the rectangle with sides $$$a$$$ and $$$b$$$ is $$$a \cdot b$$$.

Your task is to say if it is possible to create exactly $$$n$$$ rectangles of equal area or not.

You have to answer $$$q$$$ independent queries.

Input format:
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 500$$$) — the number of queries. Then $$$q$$$ queries follow.

The first line of the query contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of rectangles.

The second line of the query contains $$$4n$$$ integers $$$a_1, a_2, \dots, a_{4n}$$$ ($$$1 \le a_i \le 10^4$$$), where $$$a_i$$$ is the length of the $$$i$$$-th stick.

Output format:
For each query print the answer to it. If it is impossible to create exactly $$$n$$$ rectangles of equal area using given sticks, print "NO". Otherwise print "YES".

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

Example input:
5
1
1 1 10 10
2
10 5 2 10 1 1 2 5
2
10 5 1 10 5 1 1 1
2
1 1 1 1 1 1 1 1
1
10000 10000 10000 10000

Example output:
YES
YES
NO
YES
YES

Editorial:
After sorting $$$a$$$ we can observe that if the answer is "YES" then the area of each rectangle is $$$area = a_{1} \cdot a_{4n}$$$. Then we just need to check for each $$$i$$$ from $$$1$$$ to $$$n$$$ that $$$a_{2i-1} = a_{2i}$$$ and $$$a_{4n-2i+1} = a_{4n-2i+2}$$$ and $$$a_{2i-1} \cdot a_{4n-2i+2} = area$$$. If all conditions are satisfied for all $$$i$$$ then the answer is "YES". Otherwise the answer is "NO".