1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
A pile of stones
Contest: Codeforces Round 559 (Div. 2)
Difficulty rating: 800
Tags: implementation, math

Vasya has a pile, that consists of some number of stones. $$$n$$$ times he either took one stone from the pile or added one stone to the pile. The pile was non-empty before each operation of taking one stone from the pile.

You are given $$$n$$$ operations which Vasya has made. Find the minimal possible number of stones that can be in the pile after making these operations.

Input format:
The first line contains one positive integer $$$n$$$ — the number of operations, that have been made by Vasya ($$$1 \leq n \leq 100$$$).

The next line contains the string $$$s$$$, consisting of $$$n$$$ symbols, equal to "-" (without quotes) or "+" (without quotes). If Vasya took the stone on $$$i$$$-th operation, $$$s_i$$$ is equal to "-" (without quotes), if added, $$$s_i$$$ is equal to "+" (without quotes).

Output format:
Print one integer — the minimal possible number of stones that can be in the pile after these $$$n$$$ operations.

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

Note:
In the first test, if Vasya had $$$3$$$ stones in the pile at the beginning, after making operations the number of stones will be equal to $$$0$$$. It is impossible to have less number of piles, so the answer is $$$0$$$. Please notice, that the number of stones at the beginning can't be less, than $$$3$$$, because in this case, Vasya won't be able to take a stone on some operation (the pile will be empty).

In the second test, if Vasya had $$$0$$$ stones in the pile at the beginning, after making operations the number of stones will be equal to $$$4$$$. It is impossible to have less number of piles because after making $$$4$$$ operations the number of stones in the pile increases on $$$4$$$ stones. So, the answer is $$$4$$$.

In the third test, if Vasya had $$$1$$$ stone in the pile at the beginning, after making operations the number of stones will be equal to $$$1$$$. It can be proved, that it is impossible to have less number of stones after making the operations.

In the fourth test, if Vasya had $$$0$$$ stones in the pile at the beginning, after making operations the number of stones will be equal to $$$3$$$.

Example input:
3
---

Example output:
0

Example input:
4
++++

Example output:
4

Editorial:
Let's consider an array $$$a$$$, there $$$a_i=1$$$, if $$$s_i=$$$"+" and $$$a_i=-1$$$, if $$$s_i=$$$"-".
Let's notice, that the answer $$$\geq a_{k+1} + \ldots + a_n$$$ for all $$$k$$$. It is true, because after making the first $$$k$$$ operations the number of stones will be $$$\geq 0$$$, so at the end the number of stones will be $$$\geq a_{k+1} + \ldots + a_n$$$.
Let's prove, that the answer is equal to $$$ans = \max\limits_{0 \leq k \leq n} (a_{k+1} + \ldots + a_n)$$$. We proved that it should be at least that number of stones. It's easy to see, that if we will take $$$a_1 + \ldots + a_n - ans$$$ stones at the beginning, the pile will be non-empty each time when Vasya should take a stone and at the end, the number of stones will be equal to $$$ans$$$.
Complexity: $$$O(n)$$$.
Expansion coefficient of the array
Contest: Codeforces Round 559 (Div. 2)
Difficulty rating: 1300
Tags: implementation, math

Let's call an array of non-negative integers $$$a_1, a_2, \ldots, a_n$$$ a $$$k$$$-extension for some non-negative integer $$$k$$$ if for all possible pairs of indices $$$1 \leq i, j \leq n$$$ the inequality $$$k \cdot |i - j| \leq min(a_i, a_j)$$$ is satisfied. The expansion coefficient of the array $$$a$$$ is the maximal integer $$$k$$$ such that the array $$$a$$$ is a $$$k$$$-extension. Any array is a 0-expansion, so the expansion coefficient always exists.

You are given an array of non-negative integers $$$a_1, a_2, \ldots, a_n$$$. Find its expansion coefficient.

Input format:
The first line contains one positive integer $$$n$$$ — the number of elements in the array $$$a$$$ ($$$2 \leq n \leq 300\,000$$$). The next line contains $$$n$$$ non-negative integers $$$a_1, a_2, \ldots, a_n$$$, separated by spaces ($$$0 \leq a_i \leq 10^9$$$).

Output format:
Print one non-negative integer — expansion coefficient of the array $$$a_1, a_2, \ldots, a_n$$$.

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

Note:
In the first test, the expansion coefficient of the array $$$[6, 4, 5, 5]$$$ is equal to $$$1$$$ because $$$|i-j| \leq min(a_i, a_j)$$$, because all elements of the array satisfy $$$a_i \geq 3$$$. On the other hand, this array isn't a $$$2$$$-extension, because $$$6 = 2 \cdot |1 - 4| \leq min(a_1, a_4) = 5$$$ is false.

In the second test, the expansion coefficient of the array $$$[0, 1, 2]$$$ is equal to $$$0$$$ because this array is not a $$$1$$$-extension, but it is $$$0$$$-extension.

Example input:
4
6 4 5 5

Example output:
1

Example input:
3
0 1 2

Example output:
0

Editorial:
Let our array be a $$$k$$$-extension. All inequalities $$$k \cdot |i - j| \leq min(a_i, a_j)$$$ for $$$i \neq j$$$ can be changed to $$$k \leq \frac{min(a_i, a_j)}{|i - j|}$$$. For all $$$i = j$$$ inequalities are always true, because all numbers are non-negative.
So, the maximum possible value of $$$k$$$ is equal to the minimum of $$$\frac{min(a_i, a_j)}{|i - j|}$$$ for all $$$i < j$$$. Let's note, that $$$\frac{min(a_i, a_j)}{|i - j|} = min(\frac{a_i}{|i-j|}, \frac{a_j}{|i-j|})$$$. So, we need to take a minimum of $$$\frac{a_i}{|i-j|}$$$ for all $$$i \neq j$$$. If we will fix $$$i$$$ the minimum value for all $$$j$$$ is equal to $$$\frac{a_i}{max(i - 1, n - i)}$$$ and it is reached at the maximum denominator value, because $$$a_i \geq 0$$$.
So the answer is equal to $$$\min\limits_{1 \leq i \leq n} \frac{a_i}{max(i - 1, n - i)}$$$ and it can be simply found by linear time.
Complexity: $$$O(n)$$$.
Reverse Card (Easy Version)
Contest: Codeforces Round 942 (Div. 1)
Difficulty rating: 1400
Tags: brute force, math, number theory

The two versions are different problems. You may want to read both versions. You can make hacks only if both versions are solved.

You are given two positive integers $$$n$$$, $$$m$$$.

Calculate the number of ordered pairs $$$(a, b)$$$ satisfying the following conditions:

- $$$1\le a\le n$$$, $$$1\le b\le m$$$;
- $$$a+b$$$ is a multiple of $$$b \cdot \gcd(a,b)$$$.

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

The first line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$1\le n,m\le 2 \cdot 10^6$$$).

It is guaranteed that neither the sum of $$$n$$$ nor the sum of $$$m$$$ over all test cases exceeds $$$2 \cdot 10^6$$$.

Output format:
For each test case, print a single integer: the number of valid pairs.

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

Note:
In the first test case, only $$$(1,1)$$$ satisfies the conditions.

In the fourth test case, $$$(1,1),(2,1),(2,2),(3,1),(4,1),(5,1),(6,1),(6,2),(6,3),(7,1),(8,1),(9,1),(10,1),(10,2)$$$ satisfy the conditions.

Example input:
6
1 1
2 3
3 5
10 8
100 1233
1000000 1145141

Example output:
1
3
4
14
153
1643498

Editorial:
Denote $$$\gcd(a,b)$$$ as $$$d$$$. Assume that $$$a=pd$$$ and $$$b=qd$$$, then we know that $$$\gcd(p,q)=1$$$.
$$$(b\cdot\gcd(a,b))\mid (a+b)\iff (qd^2)\mid (pd+qd)\iff (qd)\mid (p+q)$$$.
Assume that $$$p+q=kqd$$$, then $$$p=(kd-1)q$$$. We know $$$q=1$$$ because $$$\gcd(p,q)=1$$$.
Enumerate $$$d$$$ from $$$1$$$ to $$$m$$$, we know $$$p+1=kd\le\lfloor\frac{n}{d}\rfloor+1$$$, so we add $$$\left\lfloor\frac{\lfloor\frac{n}{d}\rfloor+1}{d}\right\rfloor$$$ to answer.
In this method, $$$p=0,k=1,d=1$$$ will also be included in the answer, so we should subtract $$$1$$$ from the answer.
Time Complexity: $$$\mathcal O(\sum m)$$$.
Reverse Card (Hard Version)
Contest: Codeforces Round 942 (Div. 1)
Difficulty rating: 2200
Tags: brute force, math, number theory

The two versions are different problems. You may want to read both versions. You can make hacks only if both versions are solved.

You are given two positive integers $$$n$$$, $$$m$$$.

Calculate the number of ordered pairs $$$(a, b)$$$ satisfying the following conditions:

- $$$1\le a\le n$$$, $$$1\le b\le m$$$;
- $$$b \cdot \gcd(a,b)$$$ is a multiple of $$$a+b$$$.

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

The first line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$1\le n,m\le 2 \cdot 10^6$$$).

It is guaranteed that neither the sum of $$$n$$$ nor the sum of $$$m$$$ over all test cases exceeds $$$2 \cdot 10^6$$$.

Output format:
For each test case, print a single integer: the number of valid pairs.

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

Note:
In the first test case, no pair satisfies the conditions.

In the fourth test case, $$$(2,2),(3,6),(4,4),(6,3),(6,6),(8,8)$$$ satisfy the conditions.

Example input:
6
1 1
2 3
3 5
10 8
100 1233
1000000 1145141

Example output:
0
1
1
6
423
5933961

Editorial:
Denote $$$\gcd(a,b)$$$ as $$$d$$$. Assume that $$$a=pd$$$ and $$$b=qd$$$, then we know that $$$\gcd(p,q)=1$$$.
$$$(a+b)\mid (b\cdot\gcd(a,b))\iff (pd+qd)\mid (qd^2)\iff (p+q)\mid (qd)$$$.
We know that $$$\gcd(p+q,q)=\gcd(p,q)=1$$$, so $$$(p+q)\mid d$$$.
We also know that $$$p\ge 1,q\ge 1$$$, so $$$p < d=\frac{a}{p}\le \frac{n}{p}$$$ and thus $$$p^2 < n$$$. Similarly, we can prove $$$q^2 < m$$$.
So the number of $$$(p,q)$$$ is $$$\mathcal O(\sqrt{nm})=\mathcal O(n+m)$$$. We can enumerate each $$$(p,q)$$$ such that $$$\gcd(p,q)=1$$$ and calculate the answer. $$$(p+q)\mid d$$$ is required, so we add $$$\left\lfloor\frac{\min\{\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{q}\rfloor\}}{p+q}\right\rfloor$$$.
Time Complexity: $$$\mathcal O(\sum n + \sum m)$$$.
Two Bags of Potatoes
Contest: Codeforces Round 148 (Div. 2)
Difficulty rating: 1200
Tags: greedy, implementation, math

Valera had two bags of potatoes, the first of these bags contains x (x ≥ 1) potatoes, and the second — y (y ≥ 1) potatoes. Valera — very scattered boy, so the first bag of potatoes (it contains x potatoes) Valera lost. Valera remembers that the total amount of potatoes (x + y) in the two bags, firstly, was not gerater than n, and, secondly, was divisible by k.

Help Valera to determine how many potatoes could be in the first bag. Print all such possible numbers in ascending order.

Input format:
The first line of input contains three integers y, k, n (1 ≤ y, k, n ≤ 109; $$\pi_{k}$$  ≤ 105).

Output format:
Print the list of whitespace-separated integers — all possible values of x in ascending order. You should print each possible value of x exactly once.

If there are no such values of x print a single integer -1.

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

Example input:
10 1 10

Example output:
-1

Example input:
10 6 40

Example output:
2 8 14 20 26

Editorial:
Easy Tape Programming
Contest: Codeforces Round 148 (Div. 2)
Difficulty rating: 1500
Tags: brute force, implementation

There is a programming language in which every program is a non-empty sequence of "<" and ">" signs and digits. Let's explain how the interpreter of this programming language works. A program is interpreted using movement of instruction pointer (IP) which consists of two parts.

- Current character pointer (CP);
- Direction pointer (DP) which can point left or right;

Initially CP points to the leftmost character of the sequence and DP points to the right.

We repeat the following steps until the first moment that CP points to somewhere outside the sequence.

- If CP is pointing to a digit the interpreter prints that digit then CP moves one step according to the direction of DP. After that the value of the printed digit in the sequence decreases by one. If the printed digit was 0 then it cannot be decreased therefore it's erased from the sequence and the length of the sequence decreases by one.
- If CP is pointing to "<" or ">" then the direction of DP changes to "left" or "right" correspondingly. Then CP moves one step according to DP. If the new character that CP is pointing to is "<" or ">" then the previous character will be erased from the sequence.

If at any moment the CP goes outside of the sequence the execution is terminated.

It's obvious the every program in this language terminates after some steps.

We have a sequence s1, s2, ..., sn of "<", ">" and digits. You should answer q queries. Each query gives you l and r and asks how many of each digit will be printed if we run the sequence sl, sl + 1, ..., sr as an independent program in this language.

Input format:
The first line of input contains two integers n and q (1 ≤ n, q ≤ 100) — represents the length of the sequence s and the number of queries.

The second line contains s, a sequence of "<", ">" and digits (0..9) written from left to right. Note, that the characters of s are not separated with spaces.

The next q lines each contains two integers li and ri (1 ≤ li ≤ ri ≤ n) — the i-th query.

Output format:
For each query print 10 space separated integers: x0, x1, ..., x9 where xi equals the number of times the interpreter prints i while running the corresponding program. Print answers to the queries in the order they are given in input.

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

Example input:
7 4
1>3>22<
1 3
4 7
7 7
1 7

Example output:
0 1 0 1 0 0 0 0 0 0
2 2 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
2 3 2 1 0 0 0 0 0 0

Editorial:
Let's Watch Football
Contest: Codeforces Round 123 (Div. 2)
Difficulty rating: 1000
Tags: binary search, brute force, math

Valeric and Valerko missed the last Euro football game, so they decided to watch the game's key moments on the Net. They want to start watching as soon as possible but the connection speed is too low. If they turn on the video right now, it will "hang up" as the size of data to watch per second will be more than the size of downloaded data per second.

The guys want to watch the whole video without any pauses, so they have to wait some integer number of seconds for a part of the video to download. After this number of seconds passes, they can start watching. Waiting for the whole video to download isn't necessary as the video can download after the guys started to watch.

Let's suppose that video's length is c seconds and Valeric and Valerko wait t seconds before the watching. Then for any moment of time t0, t ≤ t0 ≤ c + t, the following condition must fulfill: the size of data received in t0 seconds is not less than the size of data needed to watch t0 - t seconds of the video.

Of course, the guys want to wait as little as possible, so your task is to find the minimum integer number of seconds to wait before turning the video on. The guys must watch the video without pauses.

Input format:
The first line contains three space-separated integers a, b and c (1 ≤ a, b, c ≤ 1000, a > b). The first number (a) denotes the size of data needed to watch one second of the video. The second number (b) denotes the size of data Valeric and Valerko can download from the Net per second. The third number (c) denotes the video's length in seconds.

Output format:
Print a single number — the minimum integer number of seconds that Valeric and Valerko must wait to watch football without pauses.

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

Note:
In the first sample video's length is 1 second and it is necessary 4 units of data for watching 1 second of video, so guys should download 4 · 1 = 4 units of data to watch the whole video. The most optimal way is to wait 3 seconds till 3 units of data will be downloaded and then start watching. While guys will be watching video 1 second, one unit of data will be downloaded and Valerik and Valerko will have 4 units of data by the end of watching. Also every moment till the end of video guys will have more data then necessary for watching.

In the second sample guys need 2 · 10 = 20 units of data, so they have to wait 5 seconds and after that they will have 20 units before the second second ends. However, if guys wait 4 seconds, they will be able to watch first second of video without pauses, but they will download 18 units of data by the end of second second and it is less then necessary.

Example input:
4 1 1

Example output:
3

Example input:
10 3 2

Example output:
5

Editorial:
After Training
Contest: Codeforces Round 123 (Div. 2)
Difficulty rating: 1300
Tags: data structures, implementation, math

After a team finished their training session on Euro football championship, Valeric was commissioned to gather the balls and sort them into baskets. Overall the stadium has n balls and m baskets. The baskets are positioned in a row from left to right and they are numbered with numbers from 1 to m, correspondingly. The balls are numbered with numbers from 1 to n.

Valeric decided to sort the balls in the order of increasing of their numbers by the following scheme. He will put each new ball in the basket with the least number of balls. And if he's got several variants, he chooses the basket which stands closer to the middle. That means that he chooses the basket for which $$\left|\frac{m+1}{2}-i\right|$$ is minimum, where i is the number of the basket. If in this case Valeric still has multiple variants, he chooses the basket with the minimum number.

For every ball print the number of the basket where it will go according to Valeric's scheme.

Note that the balls are sorted into baskets in the order of increasing numbers, that is, the first ball goes first, then goes the second ball and so on.

Input format:
The first line contains two space-separated integers n, m (1 ≤ n, m ≤ 105) — the number of balls and baskets, correspondingly.

Output format:
Print n numbers, one per line. The i-th line must contain the number of the basket for the i-th ball.

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

Example input:
4 3

Example output:
2
1
3
2

Example input:
3 1

Example output:
1
1
1

Editorial:
Analyzing Polyline
Contest: Codeforces Round 123 (Div. 2)
Difficulty rating: 1900
Tags: geometry, math, sortings

As Valeric and Valerko were watching one of the last Euro Championship games in a sports bar, they broke a mug. Of course, the guys paid for it but the barman said that he will let them watch football in his bar only if they help his son complete a programming task. The task goes like that.

Let's consider a set of functions of the following form:

$$y_i(x) = \begin{cases} 
k_i \cdot x + b_i, & \text{if } k_i \cdot x + b_i \geq 0; \\
0, & \text{if } k_i \cdot x + b_i < 0.
\end{cases}$$

Valeric and Valerko really want to watch the next Euro Championship game, so they asked you to help them.

Input format:
The first line contains integer n (1 ≤ n ≤ 105) — the number of functions. Each of the following n lines contains two space-separated integer numbers ki, bi ( - 109 ≤ ki, bi ≤ 109) that determine the i-th function.

Output format:
Print a single number — the number of angles that do not equal 180 degrees in the graph of the polyline that equals the sum of the given functions.

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

Example input:
1
1 0

Example output:
1

Example input:
3
1 0
0 2
-1 1

Example output:
2

Editorial:
Find The Array
Contest: Educational Codeforces Round 111 (Rated for Div. 2)
Difficulty rating: 800
Tags: greedy, math

Let's call an array $$$a$$$ consisting of $$$n$$$ positive (greater than $$$0$$$) integers beautiful if the following condition is held for every $$$i$$$ from $$$1$$$ to $$$n$$$: either $$$a_i = 1$$$, or at least one of the numbers $$$a_i - 1$$$ and $$$a_i - 2$$$ exists in the array as well.

For example:

- the array $$$[5, 3, 1]$$$ is beautiful: for $$$a_1$$$, the number $$$a_1 - 2 = 3$$$ exists in the array; for $$$a_2$$$, the number $$$a_2 - 2 = 1$$$ exists in the array; for $$$a_3$$$, the condition $$$a_3 = 1$$$ holds;
- the array $$$[1, 2, 2, 2, 2]$$$ is beautiful: for $$$a_1$$$, the condition $$$a_1 = 1$$$ holds; for every other number $$$a_i$$$, the number $$$a_i - 1 = 1$$$ exists in the array;
- the array $$$[1, 4]$$$ is not beautiful: for $$$a_2$$$, neither $$$a_2 - 2 = 2$$$ nor $$$a_2 - 1 = 3$$$ exists in the array, and $$$a_2 \ne 1$$$;
- the array $$$[2]$$$ is not beautiful: for $$$a_1$$$, neither $$$a_1 - 1 = 1$$$ nor $$$a_1 - 2 = 0$$$ exists in the array, and $$$a_1 \ne 1$$$;
- the array $$$[2, 1, 3]$$$ is beautiful: for $$$a_1$$$, the number $$$a_1 - 1 = 1$$$ exists in the array; for $$$a_2$$$, the condition $$$a_2 = 1$$$ holds; for $$$a_3$$$, the number $$$a_3 - 2 = 1$$$ exists in the array.

You are given a positive integer $$$s$$$. Find the minimum possible size of a beautiful array with the sum of elements equal to $$$s$$$.

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

Then $$$t$$$ lines follow, the $$$i$$$-th line contains one integer $$$s$$$ ($$$1 \le s \le 5000$$$) for the $$$i$$$-th test case.

Output format:
Print $$$t$$$ integers, the $$$i$$$-th integer should be the answer for the $$$i$$$-th testcase: the minimum possible size of a beautiful array with the sum of elements equal to $$$s$$$.

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

Note:
Consider the example test:

1. in the first test case, the array $$$[1]$$$ meets all conditions;
2. in the second test case, the array $$$[3, 4, 1]$$$ meets all conditions;
3. in the third test case, the array $$$[1, 2, 4]$$$ meets all conditions;
4. in the fourth test case, the array $$$[1, 4, 6, 8, 10, 2, 11]$$$ meets all conditions.

Example input:
4
1
8
7
42

Example output:
1
3
3
7

Editorial:
The maximum sum we can construct with $$$n$$$ elements is $$$1 + 3 + 5 + 7 + \dots + 2n-1 = n^2$$$, so we need at least $$$\lceil\sqrt{s}\rceil$$$ elements to construct the sum equal to $$$s$$$. Let's show how to express $$$s$$$ with exactly $$$\lceil\sqrt{s}\rceil$$$ elements.
Let $$$\lceil\sqrt{s}\rceil = d$$$. By taking $$$1 + 3 + 5 + 7 + \dots + 2d-3$$$, we achieve a sum of $$$(d-1)^2$$$ using $$$d - 1$$$ elements. $$$s - (d-1)^2$$$ is not less than $$$1$$$ and not greater than $$$2d-1$$$ (since $$$\sqrt{(d-1)^2} = d-1$$$, and $$$\sqrt{(d-1)^2 + 2d} > d$$$). Thus, we can just add $$$s - (d-1)^2$$$ to our array, and the sum becomes exactly $$$s$$$.
So, the solution is to find the minimum $$$n$$$ such that $$$n^2 \ge s$$$.