1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Greedy Change
Contest: Codeforces Beta Round 10
Difficulty rating: 2600
Tags: constructive algorithms

Billy investigates the question of applying greedy algorithm to different spheres of life. At the moment he is studying the application of greedy algorithm to the problem about change. There is an amount of n coins of different face values, and the coins of each value are not limited in number. The task is to collect the sum x with the minimum amount of coins. Greedy algorithm with each its step takes the coin of the highest face value, not exceeding x. Obviously, if among the coins' face values exists the face value 1, any sum x can be collected with the help of greedy algorithm. However, greedy algorithm does not always give the optimal representation of the sum, i.e. the representation with the minimum amount of coins. For example, if there are face values {1, 3, 4} and it is asked to collect the sum 6, greedy algorithm will represent the sum as 4 + 1 + 1, while the optimal representation is 3 + 3, containing one coin less. By the given set of face values find out if there exist such a sum x that greedy algorithm will collect in a non-optimal way. If such a sum exists, find out the smallest of these sums.

Input format:
The first line contains an integer n (1 ≤ n ≤ 400) — the amount of the coins' face values. The second line contains n integers ai (1 ≤ ai ≤ 109), describing the face values. It is guaranteed that a1 > a2 > ... > an and an = 1.

Output format:
If greedy algorithm collects any sum in an optimal way, output -1. Otherwise output the smallest sum that greedy algorithm collects in a non-optimal way.

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

Example input:
5
25 10 5 2 1

Example output:
-1

Example input:
3
4 3 1

Example output:
6

Editorial:
Counterexample
Contest: Codeforces Round 275 (Div. 2)
Difficulty rating: 1100
Tags: brute force, implementation, math, number theory

Your friend has recently learned about coprime numbers. A pair of numbers {a, b} is called coprime if the maximum number that divides both a and b is equal to one.

Your friend often comes up with different statements. He has recently supposed that if the pair (a, b) is coprime and the pair (b, c) is coprime, then the pair (a, c) is coprime.

You want to find a counterexample for your friend's statement. Therefore, your task is to find three distinct numbers (a, b, c), for which the statement is false, and the numbers meet the condition l ≤ a < b < c ≤ r.

More specifically, you need to find three numbers (a, b, c), such that l ≤ a < b < c ≤ r, pairs (a, b) and (b, c) are coprime, and pair (a, c) is not coprime.

Input format:
The single line contains two positive space-separated integers l, r (1 ≤ l ≤ r ≤ 1018; r - l ≤ 50).

Output format:
Print three positive space-separated integers a, b, c — three distinct numbers (a, b, c) that form the counterexample. If there are several solutions, you are allowed to print any of them. The numbers must be printed in ascending order.

If the counterexample does not exist, print the single number -1.

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

Note:
In the first sample pair (2, 4) is not coprime and pairs (2, 3) and (3, 4) are.

In the second sample you cannot form a group of three distinct integers, so the answer is -1.

In the third sample it is easy to see that numbers 900000000000000009 and 900000000000000021 are divisible by three.

Example input:
2 4

Example output:
2 3 4

Example input:
10 11

Example output:
-1

Editorial:
Friends and Presents
Contest: Codeforces Round 275 (Div. 2)
Difficulty rating: 1800
Tags: binary search, math

You have two friends. You want to present each of them several positive integers. You want to present cnt1 numbers to the first friend and cnt2 numbers to the second friend. Moreover, you want all presented numbers to be distinct, that also means that no number should be presented to both friends.

In addition, the first friend does not like the numbers that are divisible without remainder by prime number x. The second one does not like the numbers that are divisible without remainder by prime number y. Of course, you're not going to present your friends numbers they don't like.

Your task is to find such minimum number v, that you can form presents using numbers from a set 1, 2, ..., v. Of course you may choose not to present some numbers at all.

A positive integer number greater than 1 is called prime if it has no positive divisors other than 1 and itself.

Input format:
The only line contains four positive integers cnt1, cnt2, x, y (1 ≤ cnt1, cnt2 < 109; cnt1 + cnt2 ≤ 109; 2 ≤ x < y ≤ 3·104) — the numbers that are described in the statement. It is guaranteed that numbers x, y are prime.

Output format:
Print a single integer — the answer to the problem.

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

Note:
In the first sample you give the set of numbers {1, 3, 5} to the first friend and the set of numbers {2} to the second friend. Note that if you give set {1, 3, 5} to the first friend, then we cannot give any of the numbers 1, 3, 5 to the second friend.

In the second sample you give the set of numbers {3} to the first friend, and the set of numbers {1, 2, 4} to the second friend. Thus, the answer to the problem is 4.

Example input:
3 1 2 3

Example output:
5

Example input:
1 3 2 3

Example output:
4

Editorial:
Double Lexicographically Minimum
Contest: Codeforces Round 854 by cybercats (Div. 1 + Div. 2)
Difficulty rating: 1700
Tags: greedy, strings

You are given a string $$$s$$$. You can reorder the characters to form a string $$$t$$$. Define $$$t_{\mathrm{max}}$$$ to be the lexicographical maximum of $$$t$$$ and $$$t$$$ in reverse order.

Given $$$s$$$ determine the lexicographically minimum value of $$$t_{\mathrm{max}}$$$ over all reorderings $$$t$$$ of $$$s$$$.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases. Descriptions of test cases follow.

The first and only line of each test case contains a string $$$s$$$ ($$$1 \leq |s| \leq 10^5$$$). $$$s$$$ consists of only lowercase English letters.

It is guaranteed that the sum of $$$|s|$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case print the lexicographically minimum value of $$$t_{\mathrm{max}}$$$ over all reorderings $$$t$$$ of $$$s$$$.

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

Note:
For the first test case, there is only one reordering of $$$s$$$, namely "a".

For the second test case, there are three reorderings of $$$s$$$.

- $$$t = \mathtt{aab}$$$: $$$t_{\mathrm{max}} = \max(\mathtt{aab}, \mathtt{baa}) = \mathtt{baa}$$$
- $$$t = \mathtt{aba}$$$: $$$t_{\mathrm{max}} = \max(\mathtt{aba}, \mathtt{aba}) = \mathtt{aba}$$$
- $$$t = \mathtt{baa}$$$: $$$t_{\mathrm{max}} = \max(\mathtt{baa}, \mathtt{aab}) = \mathtt{baa}$$$

The lexicographical minimum of $$$t_{\mathrm{max}}$$$ over all cases is "aba".

Example input:
12
a
aab
abb
abc
aabb
aabbb
aaabb
abbb
abbbb
abbcc
eaga
ffcaba

Example output:
a
aba
bab
bca
abba
abbba
ababa
bbab
bbabb
bbcca
agea
acffba

Editorial:
Let's iterate all symbols of $$$s$$$ in order from smallest to largest and construct an answer $$$t_{max}$$$.
Let the current symbol be $$$x$$$.
• If there are at least $$$2$$$ remaining symbols equal to $$$x$$$, we should add them to the current prefix and suffix of $$$t_{max}$$$ and continue.
• If there are at most one other symbol $$$y$$$ is left (there are $$$x$$$ and $$$c$$$ times $$$y$$$ left in $$$s$$$) we should add $$$\lceil \frac{c}{2} \rceil$$$ symbols $$$y$$$, symbol $$$x$$$ and $$$\lfloor \frac{c}{2} \rfloor$$$ symbols $$$y$$$ to the prefix of $$$t_{max}$$$ and break.
• Otherwise we should add all remaining symbols of $$$s$$$ (excluding $$$x$$$) to prefix of $$$t_{max}$$$ in the sorted order and after it symbol $$$x$$$.
Time complexity: $$$O(n + A)$$$, where $$$A = 26$$$.
Dima and Figure
Contest: Codeforces Round 167 (Div. 1)
Difficulty rating: 2400
Tags: dp

Dima loves making pictures on a piece of squared paper. And yet more than that Dima loves the pictures that depict one of his favorite figures.

A piece of squared paper of size n × m is represented by a table, consisting of n rows and m columns. All squares are white on blank squared paper. Dima defines a picture as an image on a blank piece of paper, obtained by painting some squares black.

The picture portrays one of Dima's favorite figures, if the following conditions hold:

- The picture contains at least one painted cell;
- All painted cells form a connected set, that is, you can get from any painted cell to any other one (you can move from one cell to a side-adjacent one);
- The minimum number of moves needed to go from the painted cell at coordinates (x1, y1) to the painted cell at coordinates (x2, y2), moving only through the colored cells, equals |x1 - x2| + |y1 - y2|.

Now Dima is wondering: how many paintings are on an n × m piece of paper, that depict one of his favorite figures? Count this number modulo 1000000007 (109 + 7).

Input format:
The first line contains two integers n and m — the sizes of the piece of paper (1 ≤ n, m ≤ 150).

Output format:
In a single line print the remainder after dividing the answer to the problem by number 1000000007 (109 + 7).

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

Example input:
2 2

Example output:
13

Example input:
3 4

Example output:
571

Editorial:
Dima and Game
Contest: Codeforces Round 167 (Div. 1)
Difficulty rating: 2600
Tags: dp, games

Dima and Anya love playing different games. Now Dima has imagined a new game that he wants to play with Anya.

Dima writes n pairs of integers on a piece of paper (li, ri) (1 ≤ li < ri ≤ p). Then players take turns. On his turn the player can do the following actions:

1. choose the number of the pair i (1 ≤ i ≤ n), such that ri - li > 2;
2. replace pair number i by pair $$( l _ { i } + \left\lfloor \frac { r _ { i } - l _ { i } } { 3 } \right\rfloor, l _ { i } + 2 \cdot \left\lfloor \frac { r _ { i } - l _ { i } } { 3 } \right\rfloor )$$ or by pair $$( l _ { i }, r _ { i } - \left\lfloor \frac { r _ { i } - l _ { i } } { 3 } \right\rfloor )$$. Notation ⌊x⌋ means rounding down to the closest integer.

The player who can't make a move loses.

Of course, Dima wants Anya, who will move first, to win. That's why Dima should write out such n pairs of integers (li, ri) (1 ≤ li < ri ≤ p), that if both players play optimally well, the first one wins. Count the number of ways in which Dima can do it. Print the remainder after dividing the answer by number 1000000007 (109 + 7).

Two ways are considered distinct, if the ordered sequences of the written pairs are distinct.

Input format:
The first line contains two integers n, p (1 ≤ n ≤ 1000, 1 ≤ p ≤ 109). The numbers are separated by a single space.

Output format:
In a single line print the remainder after dividing the answer to the problem by number 1000000007 (109 + 7).

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

Example input:
2 2

Example output:
0

Example input:
4 4

Example output:
520

Editorial:
Domino (easy version)
Contest: Codeforces Round 734 (Div. 3)
Difficulty rating: 1700
Tags: constructive algorithms, math

The only difference between this problem and D2 is that you don't have to provide the way to construct the answer in this problem, but you have to do it in D2.

There's a table of $$$n \times m$$$ cells ($$$n$$$ rows and $$$m$$$ columns). The value of $$$n \cdot m$$$ is even.

A domino is a figure that consists of two cells having a common side. It may be horizontal (one of the cells is to the right of the other) or vertical (one of the cells is above the other).

You need to find out whether it is possible to place $$$\frac{nm}{2}$$$ dominoes on the table so that exactly $$$k$$$ of them are horizontal and all the other dominoes are vertical. The dominoes cannot overlap and must fill the whole table.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case consists of a single line. The line contains three integers $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le n,m \le 100$$$, $$$0 \le k \le \frac{nm}{2}$$$, $$$n \cdot m$$$ is even) — the number of rows, columns and horizontal dominoes, respectively.

Output format:
For each test case output "YES", if it is possible to place dominoes in the desired way, or "NO" otherwise.

You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).

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

Example input:
8
4 4 2
2 3 0
3 2 3
1 2 0
2 4 2
5 2 2
2 17 16
2 1 1

Example output:
YES
YES
YES
NO
YES
NO
YES
NO

Editorial:
See the tutorial for problem D2.
Morning Sandwich
Contest: Educational Codeforces Round 152 (Rated for Div. 2)
Difficulty rating: 800
Tags: implementation, math

Monocarp always starts his morning with a good ol' sandwich. Sandwiches Monocarp makes always consist of bread, cheese and/or ham.

A sandwich always follows the formula:

- a piece of bread
- a slice of cheese or ham
- a piece of bread
- $$$\dots$$$
- a slice of cheese or ham
- a piece of bread

So it always has bread on top and at the bottom, and it alternates between bread and filling, where filling is a slice of either cheese or ham. Each piece of bread and each slice of cheese or ham is called a layer.

Today Monocarp woke up and discovered that he has $$$b$$$ pieces of bread, $$$c$$$ slices of cheese and $$$h$$$ slices of ham. What is the maximum number of layers his morning sandwich can have?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of testcases.

Each testcase consists of three integers $$$b, c$$$ and $$$h$$$ ($$$2 \le b \le 100$$$; $$$1 \le c, h \le 100$$$) — the number of pieces of bread, slices of cheese and slices of ham, respectively.

Output format:
For each testcase, print a single integer — the maximum number of layers Monocarp's morning sandwich can have.

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

Note:
In the first testcase, Monocarp can arrange a sandwich with three layers: either a piece of bread, a slice of cheese and another piece of bread, or a piece of bread, a slice of ham and another piece of bread.

In the second testcase, Monocarp has a lot of bread, but not too much filling. He can arrange a sandwich with four pieces of bread, one slice of cheese and two slices of ham.

In the third testcase, it's the opposite — Monocarp has a lot of filling, but not too much bread. He can arrange a sandwich with three pieces of bread and two slices of cheese, for example.

Example input:
3
2 1 1
10 1 2
3 7 8

Example output:
3
7
5

Editorial:
Notice that the type of filling doesn't matter. We can treat both cheese and ham together as one filling, with quantity $$$c + h$$$.
Then let's start building a sandwich layer by layer. Put a piece of bread. Then put a layer of filling and a piece of bread. Then another layer of filling and a piece of bread. Observe that you can add one layer of filling and one piece of bread until one of them runs out. After you've done that $$$k$$$ times, you placed $$$k + 1$$$ layers of bread and $$$k$$$ layers of filling.
Thus, there are two general cases. If bread runs out first, then $$$k = b - 1$$$. Otherwise, $$$k = c + h$$$. The one that runs out first is the smaller of these two values. So the answer is $$$min(b - 1, c + h)$$$.
Overall complexity: $$$O(1)$$$ per testcase.
Monsters
Contest: Educational Codeforces Round 152 (Rated for Div. 2)
Difficulty rating: 1000
Tags: greedy, math, sortings

Monocarp is playing yet another computer game. And yet again, his character is killing some monsters. There are $$$n$$$ monsters, numbered from $$$1$$$ to $$$n$$$, and the $$$i$$$-th of them has $$$a_i$$$ health points initially.

Monocarp's character has an ability that deals $$$k$$$ damage to the monster with the highest current health. If there are several of them, the one with the smaller index is chosen. If a monster's health becomes less than or equal to $$$0$$$ after Monocarp uses his ability, then it dies.

Monocarp uses his ability until all monsters die. Your task is to determine the order in which monsters will die.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$1 \le k \le 10^9$$$) — the number of monsters and the damage which Monocarp's ability deals.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the initial health points of monsters.

The sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, print $$$n$$$ integers — the indices of monsters in the order they die.

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

Note:
In the first example, the health points change as follows: $$$[1, 2, \underline{3}] \rightarrow [1, \underline{2}, 1] \rightarrow [\underline{1}, 0, 1] \rightarrow [-1, 0, \underline{1}] \rightarrow [-1, 0, -1]$$$. The monster that is going to take damage the next time Monocarp uses his ability is underlined.

In the second example, the health points change as follows: $$$[\underline{1}, 1] \rightarrow [-2, \underline{1}] \rightarrow [-2, -2]$$$.

In the third example, the health points change as follows: $$$[2, \underline{8}, 3, 5] \rightarrow [2, \underline{5}, 3, 5] \rightarrow [2, 2, 3, \underline{5}] \rightarrow [2, 2, \underline{3}, 2] \rightarrow [\underline{2}, 2, 0, 2] \rightarrow [-1, \underline{2}, 0, 2] \rightarrow [-1, -1, 0, \underline{2}] \rightarrow [-1, -1, 0, -1]$$$.

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

Example output:
2 1 3 
1 2 
3 1 2 4

Editorial:
Let's simulate the game process until the number of health points of each monster becomes $$$k$$$ or less. Then we can consider that the $$$i$$$-th monster has $$$a_i \bmod k$$$ health instead of $$$a_i$$$ (except for the case when $$$a_i$$$ is divisible by $$$k$$$, then the remaining health is $$$k$$$, not $$$0$$$).
Now, the health points of all monsters are from $$$1$$$ to $$$k$$$, so each time we damage a monster, we kill it. Therefore, monsters with $$$k$$$ health points will die first, then the ones with $$$k-1$$$ health points, and so on. So, let's sort the monsters by their remaining health points in descending order (don't forget that, if two monsters have the same health, then they should be compared by index). And the order you get after sorting is the answer to the problem.
Perfect Pair
Contest: Codeforces Round 188 (Div. 1)
Difficulty rating: 1600
Tags: brute force

Let us call a pair of integer numbers m-perfect, if at least one number in the pair is greater than or equal to m. Thus, the pairs (3, 3) and (0, 2) are 2-perfect while the pair (-1, 1) is not.

Two integers x, y are written on the blackboard. It is allowed to erase one of them and replace it with the sum of the numbers, (x + y).

What is the minimum number of such operations one has to perform in order to make the given pair of integers m-perfect?

Input format:
Single line of the input contains three integers x, y and m ( - 1018 ≤ x, y, m ≤ 1018).

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

Output format:
Print the minimum number of operations or "-1" (without quotes), if it is impossible to transform the given pair to the m-perfect one.

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

Note:
In the first sample the following sequence of operations is suitable: (1, 2) $$\rightarrow$$ (3, 2) $$\rightarrow$$ (5, 2).

In the second sample: (-1, 4) $$\rightarrow$$ (3, 4) $$\rightarrow$$ (7, 4) $$\rightarrow$$ (11, 4) $$\rightarrow$$ (15, 4).

Finally, in the third sample x, y cannot be made positive, hence there is no proper sequence of operations.

Example input:
1 2 5

Example output:
2

Example input:
-1 4 15

Example output:
4

Editorial:
Ants
Contest: Codeforces Round 188 (Div. 1)
Difficulty rating: 2000
Tags: brute force, implementation

It has been noted that if some ants are put in the junctions of the graphene integer lattice then they will act in the following fashion: every minute at each junction (x, y) containing at least four ants a group of four ants will be formed, and these four ants will scatter to the neighbouring junctions (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1) — one ant in each direction. No other ant movements will happen. Ants never interfere with each other.

Scientists have put a colony of n ants into the junction (0, 0) and now they wish to know how many ants will there be at some given junctions, when the movement of the ants stops.

Input format:
First input line contains integers n (0 ≤ n ≤ 30000) and t (1 ≤ t ≤ 50000), where n is the number of ants in the colony and t is the number of queries. Each of the next t lines contains coordinates of a query junction: integers xi, yi ( - 109 ≤ xi, yi ≤ 109). Queries may coincide.

It is guaranteed that there will be a certain moment of time when no possible movements can happen (in other words, the process will eventually end).

Output format:
Print t integers, one per line — the number of ants at the corresponding junctions when the movement of the ants stops.

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

Note:
In the first sample the colony consists of the one ant, so nothing happens at all.

In the second sample the colony consists of 6 ants. At the first minute 4 ants scatter from (0, 0) to the neighbouring junctions. After that the process stops.

Example input:
1 3
0 1
0 0
0 -1

Example output:
0
1
0

Example input:
6 5
0 -2
0 -1
0 0
0 1
0 2

Example output:
0
1
2
1
0

Editorial:
Balance
Contest: Codeforces Round 188 (Div. 1)
Difficulty rating: 2500
Tags: constructive algorithms, dfs and similar, graphs, trees

A system of n vessels with water is given. Several pairs of vessels are connected by tubes with transfusion mechanisms. One may transfer an integer amount of liters of water between two vessels connected by such tube (tube works in both directions). There might be multiple tubes between two vessels. Total number of tubes equals e. Volume of each vessel equals v liters. Of course, the amount of the water in any vessel cannot exceed v liters in the process of transfusions.

Given the initial amounts ai of water in the vessels and the desired amounts bi find a sequence of transfusions that deals with the task. Total number of transfusions must not exceed 2·n2.

Input format:
First line of the input contains integers n, v, e (1 ≤ n ≤ 300, 1 ≤ v ≤ 109, 0 ≤ e ≤ 50000).

Next two lines contain n integers each: initial ai and the desired amounts bi of water in corresponding vessels (0 ≤ ai, bi ≤ v).

Next e lines describe one tube each in the format x y (1 ≤ x, y ≤ n, x ≠ y) for a tube between vessels number x and y. There might be multiple tubes between two vessels. You may assume that vessels are numbered from 1 to n in some way.

Output format:
Print "NO" (without quotes), if such sequence of transfusions does not exist.

Otherwise print any suitable sequence in the following format. On the first line print the total number of transfusions k (k should not exceed 2·n2). In the following k lines print transfusions in the format x y d (transfusion of d liters from the vessel number x to the vessel number y, x and y must be distinct). For all transfusions d must be a non-negative integer.

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

Example input:
2 10 1
1 9
5 5
1 2

Example output:
1
2 1 4

Example input:
2 10 0
5 2
4 2

Example output:
NO

Editorial: