1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Minimum Product
Contest: Codeforces Round 667 (Div. 3)
Difficulty rating: 1100
Tags: brute force, greedy, math

You are given four integers $$$a$$$, $$$b$$$, $$$x$$$ and $$$y$$$. Initially, $$$a \ge x$$$ and $$$b \ge y$$$. You can do the following operation no more than $$$n$$$ times:

- Choose either $$$a$$$ or $$$b$$$ and decrease it by one. However, as a result of this operation, value of $$$a$$$ cannot become less than $$$x$$$, and value of $$$b$$$ cannot become less than $$$y$$$.

Your task is to find the minimum possible product of $$$a$$$ and $$$b$$$ ($$$a \cdot b$$$) you can achieve by applying the given operation no more than $$$n$$$ times.

You have to answer $$$t$$$ independent test cases.

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

The only line of the test case contains five integers $$$a$$$, $$$b$$$, $$$x$$$, $$$y$$$ and $$$n$$$ ($$$1 \le a, b, x, y, n \le 10^9$$$). Additional constraint on the input: $$$a \ge x$$$ and $$$b \ge y$$$ always holds.

Output format:
For each test case, print one integer: the minimum possible product of $$$a$$$ and $$$b$$$ ($$$a \cdot b$$$) you can achieve by applying the given operation no more than $$$n$$$ times.

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

Note:
In the first test case of the example, you need to decrease $$$b$$$ three times and obtain $$$10 \cdot 7 = 70$$$.

In the second test case of the example, you need to decrease $$$a$$$ one time, $$$b$$$ one time and obtain $$$11 \cdot 7 = 77$$$.

In the sixth test case of the example, you need to decrease $$$a$$$ five times and obtain $$$5 \cdot 11 = 55$$$.

In the seventh test case of the example, you need to decrease $$$b$$$ ten times and obtain $$$10 \cdot 1 = 10$$$.

Example input:
7
10 10 8 5 3
12 8 8 7 2
12343 43 4543 39 123212
1000000000 1000000000 1 1 1
1000000000 1000000000 1 1 1000000000
10 11 2 1 5
10 11 9 1 10

Example output:
70
77
177177
999999999000000000
999999999
55
10

Editorial:
The only fact required to solve the problem: if we start decreasing the number, we are better to end decreasing it and only then decrease the other number. So, we can just consider two cases: when we decrease $$$a$$$ first, and $$$b$$$ after that and vice versa, and just take the minimum product of these two results. The rest is just implementation.
Decrease the Sum of Digits
Contest: Codeforces Round 667 (Div. 3)
Difficulty rating: 1500
Tags: greedy, math

You are given a positive integer $$$n$$$. In one move, you can increase $$$n$$$ by one (i.e. make $$$n := n + 1$$$). Your task is to find the minimum number of moves you need to perform in order to make the sum of digits of $$$n$$$ be less than or equal to $$$s$$$.

You have to answer $$$t$$$ independent test cases.

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

The only line of the test case contains two integers $$$n$$$ and $$$s$$$ ($$$1 \le n \le 10^{18}$$$; $$$1 \le s \le 162$$$).

Output format:
For each test case, print the answer: the minimum number of moves you need to perform in order to make the sum of digits of $$$n$$$ be less than or equal to $$$s$$$.

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

Example input:
5
2 1
1 1
500 4
217871987498122 10
100000000000000001 1

Example output:
8
0
500
2128012501878
899999999999999999

Editorial:
Firstly, let's check if the initial $$$n$$$ fits the conditions. If it is, print $$$0$$$ and continue. Otherwise, let's solve the problem greedily. At first, let's try to set the last digit to zero. Let $$$dig = n \mod 10$$$. We need exactly $$$(10 - dig) \mod 10$$$ moves to do that. Let's add this number to $$$n$$$ and to the answer and check if the current $$$n$$$ fits the conditions. If it isn't, let's try to set the previous last digit to zero. Let $$$dig = \left\lfloor\frac{n}{10}\right\rfloor \mod 10$$$. Then we need $$$((10 - dig) \mod 10) \cdot 10$$$ moves to do that. Let's add this number to $$$n$$$ and to the answer and check if the current $$$n$$$ fits the conditions. If it isn't, repeat the same with the third digit and so on. This cycle can do no more than $$$18$$$ iterations. And we can fing the sum of digits of $$$n$$$ in at most $$$18$$$ iterations too (decimal logarithm of $$$n$$$).
So, the total time complexity is $$$O(\log_{10}^2{(n)})$$$.
Jellyfish and Undertale
Contest: Codeforces Round 901 (Div. 2)
Difficulty rating: 900
Tags: brute force, greedy

Flowey has planted a bomb in Snowdin!

The bomb has a timer that is initially set to $$$b$$$. Every second, the timer will decrease by $$$1$$$. When the timer reaches $$$0$$$, the bomb will explode! To give the residents of Snowdin enough time to evacuate, you will need to delay the bomb from exploding for as long as possible.

You have $$$n$$$ tools. Each tool can only be used at most once. If you use the $$$i$$$-th tool, the timer will increase by $$$x_i$$$. However, if the timer is changed to an integer larger than $$$a$$$, the timer will be set to $$$a$$$ due to a bug.

More specifically, the following events will happen every second in the following order:

1. You will choose some (possibly none) of your tools that have not been used before. If you choose the $$$i$$$-th tool, and the bomb's timer is currently set to $$$c$$$, the timer will be changed to $$$\min(c + x_i, a)$$$.
2. The timer decreases by $$$1$$$.
3. If the timer reaches $$$0$$$, the bomb explodes.

Jellyfish now wants to know the maximum time in seconds until the bomb explodes if the tools are used optimally.

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

The first line of each test case contains three integers $$$a$$$, $$$b$$$ and $$$n$$$ ($$$1 \leq b \leq a \leq 10^9$$$, $$$1 \leq n \leq 100$$$) — the maximum value of the bomb's timer, the initial value of the timer of the bomb and the number of tools.

The second line of each test contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$1 \leq x_i \leq 10^9$$$) — the number the timer can increase by using the $$$i$$$-th tool.

Note that the sum of $$$n$$$ over all test cases is not bounded.

Output format:
For each test case, output a single integer — the maximum time in seconds until the bomb explodes.

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

Note:
Let $$$c$$$ denote the value of the bomb's timer. In the first test case:

- Second $$$1$$$: choose tool $$$1$$$ and $$$2$$$ at this second, then $$$c=5$$$; the timer decreases by $$$1$$$, then $$$c=4$$$.
- Second $$$2$$$: the timer decreases by $$$1$$$, then $$$c=3$$$.
- Second $$$3$$$: the timer decreases by $$$1$$$, then $$$c=2$$$.
- Second $$$4$$$: the timer decreases by $$$1$$$, then $$$c=1$$$.
- Second $$$5$$$: choose tool $$$3$$$, then $$$c=5$$$; the timer decreases by $$$1$$$, then $$$c=4$$$.
- Second $$$6$$$: the timer decreases by $$$1$$$, then $$$c=3$$$.
- Second $$$7$$$: the timer decreases by $$$1$$$, then $$$c=2$$$.
- Second $$$8$$$: the timer decreases by $$$1$$$, then $$$c=1$$$.
- Second $$$9$$$: the timer decreases by $$$1$$$, then $$$c=0$$$. The bomb explodes.

It can be proved that there is no way to use the tools such that the bomb explodes after more than $$$9$$$ seconds.

Example input:
2
5 3 3
1 1 7
7 1 5
1 2 5 6 8

Example output:
9
21

Editorial:
Little Elephant and Interval
Contest: Codeforces Round 129 (Div. 1)
Difficulty rating: 1500
Tags: binary search, combinatorics, dp

The Little Elephant very much loves sums on intervals.

This time he has a pair of integers l and r (l ≤ r). The Little Elephant has to find the number of such integers x (l ≤ x ≤ r), that the first digit of integer x equals the last one (in decimal notation). For example, such numbers as 101, 477474 or 9 will be included in the answer and 47, 253 or 1020 will not.

Help him and count the number of described numbers x for a given pair l and r.

Input format:
The single line contains a pair of integers l and r (1 ≤ l ≤ r ≤ 1018) — the boundaries of the interval.

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:
On a single line print a single integer — the answer to the problem.

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

Note:
In the first sample the answer includes integers 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44.

Example input:
2 47

Example output:
12

Example input:
47 1024

Example output:
98

Editorial:
Little Elephant and Cards
Contest: Codeforces Round 129 (Div. 1)
Difficulty rating: 1500
Tags: binary search, data structures

The Little Elephant loves to play with color cards.

He has n cards, each has exactly two colors (the color of the front side and the color of the back side). Initially, all the cards lay on the table with the front side up. In one move the Little Elephant can turn any card to the other side. The Little Elephant thinks that a set of cards on the table is funny if at least half of the cards have the same color (for each card the color of the upper side is considered).

Help the Little Elephant to find the minimum number of moves needed to make the set of n cards funny.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 105) — the number of the cards. The following n lines contain the description of all cards, one card per line. The cards are described by a pair of positive integers not exceeding 109 — colors of both sides. The first number in a line is the color of the front of the card, the second one — of the back. The color of the front of the card may coincide with the color of the back of the card.

The numbers in the lines are separated by single spaces.

Output format:
On a single line print a single integer — the sought minimum number of moves. If it is impossible to make the set funny, print -1.

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

Note:
In the first sample there initially are three cards lying with colors 4, 4, 7. Since two of the three cards are of the same color 4, you do not need to change anything, so the answer is 0.

In the second sample, you can turn the first and the fourth cards. After that three of the five cards will be of color 7.

Example input:
3
4 7
4 7
7 4

Example output:
0

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

Example output:
2

Editorial:
Little Elephant and Furik and Rubik
Contest: Codeforces Round 129 (Div. 1)
Difficulty rating: 2000
Tags: math, probabilities

Little Elephant loves Furik and Rubik, who he met in a small city Kremenchug.

The Little Elephant has two strings of equal length a and b, consisting only of uppercase English letters. The Little Elephant selects a pair of substrings of equal length — the first one from string a, the second one from string b. The choice is equiprobable among all possible pairs. Let's denote the substring of a as x, and the substring of b — as y. The Little Elephant gives string x to Furik and string y — to Rubik.

Let's assume that f(x, y) is the number of such positions of i (1 ≤ i ≤ |x|), that xi = yi (where |x| is the length of lines x and y, and xi, yi are the i-th characters of strings x and y, correspondingly). Help Furik and Rubik find the expected value of f(x, y).

Input format:
The first line contains a single integer n (1 ≤ n ≤ 2·105) — the length of strings a and b. The second line contains string a, the third line contains string b. The strings consist of uppercase English letters only. The length of both strings equals n.

Output format:
On a single line print a real number — the answer to the problem. The answer will be considered correct if its relative or absolute error does not exceed 10 - 6.

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

Note:
Let's assume that we are given string a = a1a2... a|a|, then let's denote the string's length as |a|, and its i-th character — as ai.

A substring a[l... r] (1 ≤ l ≤ r ≤ |a|) of string a is string alal + 1... ar.

String a is a substring of string b, if there exists such pair of integers l and r (1 ≤ l ≤ r ≤ |b|), that b[l... r] = a.

Let's consider the first test sample. The first sample has 5 possible substring pairs: ("A", "B"), ("A", "A"), ("B", "B"), ("B", "A"), ("AB", "BA"). For the second and third pair value f(x, y) equals 1, for the rest it equals 0. The probability of choosing each pair equals $$\frac{1}{5}$$, that's why the answer is $$\frac{1}{5}$$ · 0  +  $$\frac{1}{5}$$ · 1  +  $$\frac{1}{5}$$ · 1  +  $$\frac{1}{5}$$ · 0  +  $$\frac{1}{5}$$ · 0  =  $$\frac{2}{5}$$  =  0.4.

Example input:
2
AB
BA

Example output:
0.400000000

Example input:
3
AAB
CAA

Example output:
0.642857143

Editorial:
Little Elephant and Retro Strings
Contest: Codeforces Round 129 (Div. 1)
Difficulty rating: 2400
Tags: dp

The Little Elephant has found a ragged old black-and-white string s on the attic.

The characters of string s are numbered from the left to the right from 1 to |s|, where |s| is the length of the string. Let's denote the i-th character of string s as si. As the string is black-and-white, each character of the string is either letter "B", or letter "W". Unfortunately, the string is very old and some characters are damaged. The damaged positions are denoted as "X".

The Little Elephant in determined to restore the string and hang it on the wall. For that he needs to replace each character "X" by a "B" or a "W". The string must look good on the wall, so it must be beautiful. The Little Elephant considers a string beautiful if it has two non-intersecting substrings of a given length k, such that the left one fully consists of characters "B", and the right one fully consists of characters "W". More formally, there are four integers a, b, c, d (1 ≤ a ≤ b < c ≤ d ≤ |s|; b - a + 1 = d - c + 1 = k) such that si = "B" (a ≤ i ≤ b) and sj = "W" (c ≤ j ≤ d).

Help the Little Elephant find the number of different beautiful strings he can obtain from string s. Two strings are considered different if there is such position, where the character in the first string differs from the corresponding character in the second string. If this string doesn't contain characters «X» and it is already beautiful — the answer is 1.

As the answer can be rather large, print it modulo 1000000007 (109 + 7).

Input format:
The first line contains two space-separated integers n and k (1 ≤ k ≤ n ≤ 106). The second line contains string s. String s has length n and only consists of characters "W", "B" and "X".

Output format:
On a single line print an integer — the answer to the problem modulo 1000000007 (109 + 7).

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

Example input:
3 2
XXX

Example output:
0

Example input:
4 2
XXXX

Example output:
1

Editorial:
Little Elephant and Strings
Contest: Codeforces Round 129 (Div. 1)
Difficulty rating: 2800
Tags: data structures, implementation, string suffix structures, two pointers

The Little Elephant loves strings very much.

He has an array a from n strings, consisting of lowercase English letters. Let's number the elements of the array from 1 to n, then let's denote the element number i as ai. For each string ai (1 ≤ i ≤ n) the Little Elephant wants to find the number of pairs of integers l and r (1 ≤ l ≤ r ≤ |ai|) such that substring ai[l... r] is a substring to at least k strings from array a (including the i-th string).

Help the Little Elephant solve this problem.

If you are not familiar with the basic notation in string problems, you can find the corresponding definitions in the notes.

Input format:
The first line contains two space-separated integers — n and k (1 ≤ n, k ≤ 105). Next n lines contain array a. The i-th line contains a non-empty string ai, consisting of lowercase English letter. The total length of all strings ai does not exceed 105.

Output format:
On a single line print n space-separated integers — the i-th number is the answer for string ai.

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.

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

Note:
Let's assume that you are given string a = a1a2... a|a|, then let's denote the string's length as |a| and the string's i-th character as ai.

A substring a[l... r] (1 ≤ l ≤ r ≤ |a|) of string a is string alal + 1... ar.

String a is a substring of string b, if there exists such pair of integers l and r (1 ≤ l ≤ r ≤ |b|), that b[l... r] = a.

Example input:
3 1
abc
a
ab

Example output:
6 1 3

Example input:
7 4
rubik
furik
abab
baba
aaabbbababa
abababababa
zero

Example output:
1 0 9 9 21 30 0

Editorial:
Mean Inequality
Contest: Codeforces Round 723 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, sortings

You are given an array $$$a$$$ of $$$2n$$$ distinct integers. You want to arrange the elements of the array in a circle such that no element is equal to the the arithmetic mean of its $$$2$$$ neighbours.

More formally, find an array $$$b$$$, such that:

- $$$b$$$ is a permutation of $$$a$$$.
- For every $$$i$$$ from $$$1$$$ to $$$2n$$$, $$$b_i \neq \frac{b_{i-1}+b_{i+1}}{2}$$$, where $$$b_0 = b_{2n}$$$ and $$$b_{2n+1} = b_1$$$.

It can be proved that under the constraints of this problem, such array $$$b$$$ always exists.

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

The first line of each testcase contains a single integer $$$n$$$ $$$(1 \leq n \leq 25)$$$.

The second line of each testcase contains $$$2n$$$ integers $$$a_1, a_2, \ldots, a_{2n}$$$ $$$(1 \leq a_i \leq 10^9)$$$ — elements of the array.

Note that there is no limit to the sum of $$$n$$$ over all testcases.

Output format:
For each testcase, you should output $$$2n$$$ integers, $$$b_1, b_2, \ldots b_{2n}$$$, for which the conditions from the statement are satisfied.

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

Note:
In the first testcase, array $$$[3, 1, 4, 2, 5, 6]$$$ works, as it's a permutation of $$$[1, 2, 3, 4, 5, 6]$$$, and $$$\frac{3+4}{2}\neq 1$$$, $$$\frac{1+2}{2}\neq 4$$$, $$$\frac{4+5}{2}\neq 2$$$, $$$\frac{2+6}{2}\neq 5$$$, $$$\frac{5+3}{2}\neq 6$$$, $$$\frac{6+1}{2}\neq 3$$$.

Example input:
3
3
1 2 3 4 5 6
2
123 456 789 10
1
6 9

Example output:
3 1 4 2 5 6
123 10 456 789
9 6

Editorial:
I Hate 1111
Contest: Codeforces Round 723 (Div. 2)
Difficulty rating: 1400
Tags: dp, math, number theory

You are given an integer $$$x$$$. Can you make $$$x$$$ by summing up some number of $$$11, 111, 1111, 11111, \ldots$$$? (You can use any number among them any number of times).

For instance,

- $$$33=11+11+11$$$
- $$$144=111+11+11+11$$$

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

The first and only line of each testcase contains a single integer $$$x$$$ $$$(1 \leq x \leq 10^9)$$$ — the number you have to make.

Output format:
For each testcase, you should output a single string. If you can make $$$x$$$, output "YES" (without quotes). Otherwise, output "NO".

You can print each letter of "YES" and "NO" in any case (upper or lower).

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

Note:
Ways to make $$$33$$$ and $$$144$$$ were presented in the statement. It can be proved that we can't present $$$69$$$ this way.

Example input:
3
33
144
69

Example output:
YES
YES
NO

Editorial:
Potions (Easy Version)
Contest: Codeforces Round 723 (Div. 2)
Difficulty rating: 1500
Tags: brute force, data structures, dp, greedy

This is the easy version of the problem. The only difference is that in this version $$$n \leq 2000$$$. You can make hacks only if both versions of the problem are solved.

There are $$$n$$$ potions in a line, with potion $$$1$$$ on the far left and potion $$$n$$$ on the far right. Each potion will increase your health by $$$a_i$$$ when drunk. $$$a_i$$$ can be negative, meaning that potion will decrease will health.

You start with $$$0$$$ health and you will walk from left to right, from first potion to the last one. At each potion, you may choose to drink it or ignore it. You must ensure that your health is always non-negative.

What is the largest number of potions you can drink?

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 2000$$$) — the number of potions.

The next line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ... ,$$$a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) which represent the change in health after drinking that potion.

Output format:
Output a single integer, the maximum number of potions you can drink without your health becoming negative.

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

Note:
For the sample, you can drink $$$5$$$ potions by taking potions $$$1$$$, $$$3$$$, $$$4$$$, $$$5$$$ and $$$6$$$. It is not possible to drink all $$$6$$$ potions because your health will go negative at some point

Example input:
6
4 -4 1 -3 1 -3

Example output:
5

Editorial:
Potions (Hard Version)
Contest: Codeforces Round 723 (Div. 2)
Difficulty rating: 1600
Tags: data structures, greedy

This is the hard version of the problem. The only difference is that in this version $$$n \leq 200000$$$. You can make hacks only if both versions of the problem are solved.

There are $$$n$$$ potions in a line, with potion $$$1$$$ on the far left and potion $$$n$$$ on the far right. Each potion will increase your health by $$$a_i$$$ when drunk. $$$a_i$$$ can be negative, meaning that potion will decrease will health.

You start with $$$0$$$ health and you will walk from left to right, from first potion to the last one. At each potion, you may choose to drink it or ignore it. You must ensure that your health is always non-negative.

What is the largest number of potions you can drink?

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 200000$$$) — the number of potions.

The next line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ... ,$$$a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) which represent the change in health after drinking that potion.

Output format:
Output a single integer, the maximum number of potions you can drink without your health becoming negative.

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

Note:
For the sample, you can drink $$$5$$$ potions by taking potions $$$1$$$, $$$3$$$, $$$4$$$, $$$5$$$ and $$$6$$$. It is not possible to drink all $$$6$$$ potions because your health will go negative at some point

Example input:
6
4 -4 1 -3 1 -3

Example output:
5

Editorial: