1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Modular Stability
Contest: Educational Codeforces Round 88 (Rated for Div. 2)
Difficulty rating: 2000
Tags: combinatorics, math, number theory

We define $$$x \bmod y$$$ as the remainder of division of $$$x$$$ by $$$y$$$ ($$$\%$$$ operator in C++ or Java, mod operator in Pascal).

Let's call an array of positive integers $$$[a_1, a_2, \dots, a_k]$$$ stable if for every permutation $$$p$$$ of integers from $$$1$$$ to $$$k$$$, and for every non-negative integer $$$x$$$, the following condition is met:

$$$ (((x \bmod a_1) \bmod a_2) \dots \bmod a_{k - 1}) \bmod a_k = (((x \bmod a_{p_1}) \bmod a_{p_2}) \dots \bmod a_{p_{k - 1}}) \bmod a_{p_k} $$$

That is, for each non-negative integer $$$x$$$, the value of $$$(((x \bmod a_1) \bmod a_2) \dots \bmod a_{k - 1}) \bmod a_k$$$ does not change if we reorder the elements of the array $$$a$$$.

For two given integers $$$n$$$ and $$$k$$$, calculate the number of stable arrays $$$[a_1, a_2, \dots, a_k]$$$ such that $$$1 \le a_1 < a_2 < \dots < a_k \le n$$$.

Input format:
The only line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 5 \cdot 10^5$$$).

Output format:
Print one integer — the number of stable arrays $$$[a_1, a_2, \dots, a_k]$$$ such that $$$1 \le a_1 < a_2 < \dots < a_k \le n$$$. Since the answer may be large, print it modulo $$$998244353$$$.

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

Example input:
7 3

Example output:
16

Example input:
3 7

Example output:
0

Editorial:
We claim that the array is stable if and only if all elements are divisible by its minimum. The proof of this fact will be at the end of the editorial.
To calculate the number of stable arrays now, we need to iterate on the minimum in the array and choose the remaining elements so that they are multiples of it. If the minimum is $$$i$$$, then the resulting elements should be divisible by $$$i$$$. There are $$$d = \lfloor\frac{n}{i}\rfloor$$$ such numbers between $$$1$$$ and $$$n$$$, and we have to choose $$$k - 1$$$ elements out of $$$d - 1$$$ (since $$$i$$$ is already chosen). The number of ways to do it can be calculated by precomputing factorials modulo $$$998244353$$$, since it is a binomial coefficient.
Proof of the claim at the beginning of the editorial:
On the one hand, since $$$(x \bmod a) \bmod (ba) = (x \bmod (ba)) \bmod a = x \bmod a$$$, if all elements in the array are divisible by some element, nothing depends on the order of these elements.
On the other hand, suppose there exists an element $$$a_i$$$ such that it is not divisible by $$$a_1$$$. Let's take $$$x = a_i$$$ and two following reorders of the array $$$a$$$: $$$[a_1, a_2, \dots, a_k]$$$ and $$$[a_i, a_1, a_2, \dots, a_{i - 1}, a_{i + 1}, \dots, a_k]$$$. For the first array, we get $$$x \bmod a_1 = a_i \bmod a_1$$$, which is non-zero; and for the second array, $$$a_i \bmod a_i = 0$$$, so the result is zero.
Is it rated?
Contest: Codeforces Round 412 (rated, Div. 2, base on VK Cup 2017 Round 3)
Difficulty rating: 900
Tags: implementation, sortings

Is it rated?

Here it is. The Ultimate Question of Competitive Programming, Codeforces, and Everything. And you are here to answer it.

Another Codeforces round has been conducted. No two participants have the same number of points. For each participant, from the top to the bottom of the standings, their rating before and after the round is known.

It's known that if at least one participant's rating has changed, then the round was rated for sure.

It's also known that if the round was rated and a participant with lower rating took a better place in the standings than a participant with higher rating, then at least one round participant's rating has changed.

In this problem, you should not make any other assumptions about the rating system.

Determine if the current round is rated, unrated, or it's impossible to determine whether it is rated of not.

Input format:
The first line contains a single integer n (2 ≤ n ≤ 1000) — the number of round participants.

Each of the next n lines contains two integers ai and bi (1 ≤ ai, bi ≤ 4126) — the rating of the i-th participant before and after the round, respectively. The participants are listed in order from the top to the bottom of the standings.

Output format:
If the round is rated for sure, print "rated". If the round is unrated for sure, print "unrated". If it's impossible to determine whether the round is rated or not, print "maybe".

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

Note:
In the first example, the ratings of the participants in the third and fifth places have changed, therefore, the round was rated.

In the second example, no one's rating has changed, but the participant in the second place has lower rating than the participant in the fourth place. Therefore, if the round was rated, someone's rating would've changed for sure.

In the third example, no one's rating has changed, and the participants took places in non-increasing order of their rating. Therefore, it's impossible to determine whether the round is rated or not.

Example input:
6
3060 3060
2194 2194
2876 2903
2624 2624
3007 2991
2884 2884

Example output:
rated

Example input:
4
1500 1500
1300 1300
1200 1200
1400 1400

Example output:
unrated

Editorial:
To solve this problem, you just had to read the problem statement carefully. Looking through the explanations for the example cases was pretty useful.
How do we check if the round is rated for sure?
The round is rated for sure if anyone's rating has changed, that is, if ai ≠ bi for some i.
How do we check if the round is unrated for sure?
Given that all ai = bi, the round is unrated for sure if for some i < j we have ai < aj. This can be checked using two nested for-loops over i and j.
Exercise: can you check the same using one for-loop?
How do we find that it's impossible to determine if the round is rated or not?
If none of the conditions from steps 1 and 2 is satisfied, the answer is "maybe".
Tokitsukaze and Enhancement
Contest: Codeforces Round 573 (Div. 2)
Difficulty rating: 800
Tags: brute force

Tokitsukaze is one of the characters in the game "Kantai Collection". In this game, every character has a common attribute — health points, shortened to HP.

In general, different values of HP are grouped into $$$4$$$ categories:

- Category $$$A$$$ if HP is in the form of $$$(4 n + 1)$$$, that is, when divided by $$$4$$$, the remainder is $$$1$$$;
- Category $$$B$$$ if HP is in the form of $$$(4 n + 3)$$$, that is, when divided by $$$4$$$, the remainder is $$$3$$$;
- Category $$$C$$$ if HP is in the form of $$$(4 n + 2)$$$, that is, when divided by $$$4$$$, the remainder is $$$2$$$;
- Category $$$D$$$ if HP is in the form of $$$4 n$$$, that is, when divided by $$$4$$$, the remainder is $$$0$$$.

The above-mentioned $$$n$$$ can be any integer.

These $$$4$$$ categories ordered from highest to lowest as $$$A > B > C > D$$$, which means category $$$A$$$ is the highest and category $$$D$$$ is the lowest.

While playing the game, players can increase the HP of the character. Now, Tokitsukaze wants you to increase her HP by at most $$$2$$$ (that is, either by $$$0$$$, $$$1$$$ or $$$2$$$). How much should she increase her HP so that it has the highest possible category?

Input format:
The only line contains a single integer $$$x$$$ ($$$30 \leq x \leq 100$$$) — the value Tokitsukaze's HP currently.

Output format:
Print an integer $$$a$$$ ($$$0 \leq a \leq 2$$$) and an uppercase letter $$$b$$$ ($$$b \in \lbrace A, B, C, D \rbrace$$$), representing that the best way is to increase her HP by $$$a$$$, and then the category becomes $$$b$$$.

Note that the output characters are case-sensitive.

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

Note:
For the first example, the category of Tokitsukaze's HP is already $$$A$$$, so you don't need to enhance her ability.

For the second example:

- If you don't increase her HP, its value is still $$$98$$$, which equals to $$$(4 \times 24 + 2)$$$, and its category is $$$C$$$.
- If you increase her HP by $$$1$$$, its value becomes $$$99$$$, which equals to $$$(4 \times 24 + 3)$$$, and its category becomes $$$B$$$.
- If you increase her HP by $$$2$$$, its value becomes $$$100$$$, which equals to $$$(4 \times 25)$$$, and its category becomes $$$D$$$.

Therefore, the best way is to increase her HP by $$$1$$$ so that the category of her HP becomes $$$B$$$.

Example input:
33

Example output:
0 A

Example input:
98

Example output:
1 B

Editorial:
By increasing at most $$$2$$$ points, the value of her HP can always become an odd number, and thus the highest possible level is either $$$A$$$ or $$$B$$$. We can just solve case by case.
Tokitsukaze and Mahjong
Contest: Codeforces Round 573 (Div. 2)
Difficulty rating: 1200
Tags: brute force, implementation

Tokitsukaze is playing a game derivated from Japanese mahjong. In this game, she has three tiles in her hand. Each tile she owns is a suited tile, which means it has a suit (manzu, pinzu or souzu) and a number (a digit ranged from $$$1$$$ to $$$9$$$). In this problem, we use one digit and one lowercase letter, which is the first character of the suit, to represent a suited tile. All possible suited tiles are represented as 1m, 2m, $$$\ldots$$$, 9m, 1p, 2p, $$$\ldots$$$, 9p, 1s, 2s, $$$\ldots$$$, 9s.

In order to win the game, she must have at least one mentsu (described below) in her hand, so sometimes she should draw extra suited tiles. After drawing a tile, the number of her tiles increases by one. She can draw any tiles she wants, including those already in her hand.

Do you know the minimum number of extra suited tiles she needs to draw so that she can win?

Here are some useful definitions in this game:

- A mentsu, also known as meld, is formed by a koutsu or a shuntsu;
- A koutsu, also known as triplet, is made of three identical tiles, such as [1m, 1m, 1m], however, [1m, 1p, 1s] or [1m, 4m, 7m] is NOT a koutsu;
- A shuntsu, also known as sequence, is made of three sequential numbered tiles in the same suit, such as [1m, 2m, 3m] and [5s, 7s, 6s], however, [9m, 1m, 2m] or [1m, 2p, 3s] is NOT a shuntsu.

Some examples:

- [2m, 3p, 2s, 4m, 1s, 2s, 4s] — it contains no koutsu or shuntsu, so it includes no mentsu;
- [4s, 3m, 3p, 4s, 5p, 4s, 5p] — it contains a koutsu, [4s, 4s, 4s], but no shuntsu, so it includes a mentsu;
- [5p, 5s, 9m, 4p, 1s, 7p, 7m, 6p] — it contains no koutsu but a shuntsu, [5p, 4p, 6p] or [5p, 7p, 6p], so it includes a mentsu.

Note that the order of tiles is unnecessary and you can assume the number of each type of suited tiles she can draw is infinite.

Input format:
The only line contains three strings — the tiles in Tokitsukaze's hand. For each string, the first character is a digit ranged from $$$1$$$ to $$$9$$$ and the second character is m, p or s.

Output format:
Print a single integer — the minimum number of extra suited tiles she needs to draw.

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

Note:
In the first example, Tokitsukaze already has a shuntsu.

In the second example, Tokitsukaze already has a koutsu.

In the third example, Tokitsukaze can get a shuntsu by drawing one suited tile — 1p or 4p. The resulting tiles will be [3p, 9m, 2p, 1p] or [3p, 9m, 2p, 4p].

Example input:
1s 2s 3s

Example output:
0

Example input:
9m 9m 9m

Example output:
0

Editorial:
There are only two types of mentsus, so you can enumerate the mentsu you want her to form, and check the difference between that and those currently in her hand.
Alternatively, you can find out that the answer is at most $$$2$$$, since she can draw two extra identical tiles which are the same as one of those in her hand. You may enumerate at most $$$1$$$ extra tile for her and check if it can contribute to a mentsu. If she can't, the answer will be $$$2$$$.
Die Roll
Contest: Codeforces Beta Round 9 (Div. 2 Only)
Difficulty rating: 800
Tags: math, probabilities

Yakko, Wakko and Dot, world-famous animaniacs, decided to rest from acting in cartoons, and take a leave to travel a bit. Yakko dreamt to go to Pennsylvania, his Motherland and the Motherland of his ancestors. Wakko thought about Tasmania, its beaches, sun and sea. Dot chose Transylvania as the most mysterious and unpredictable place.

But to their great regret, the leave turned to be very short, so it will be enough to visit one of the three above named places. That's why Yakko, as the cleverest, came up with a truly genius idea: let each of the three roll an ordinary six-sided die, and the one with the highest amount of points will be the winner, and will take the other two to the place of his/her dreams.

Yakko thrown a die and got Y points, Wakko — W points. It was Dot's turn. But she didn't hurry. Dot wanted to know for sure what were her chances to visit Transylvania.

It is known that Yakko and Wakko are true gentlemen, that's why if they have the same amount of points with Dot, they will let Dot win.

Input format:
The only line of the input file contains two natural numbers Y and W — the results of Yakko's and Wakko's die rolls.

Output format:
Output the required probability in the form of irreducible fraction in format «A/B», where A — the numerator, and B — the denominator. If the required probability equals to zero, output «0/1». If the required probability equals to 1, output «1/1».

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

Note:
Dot will go to Transylvania, if she is lucky to roll 4, 5 or 6 points.

Example input:
4 2

Example output:
1/2

Editorial:
Running Student
Contest: Codeforces Beta Round 9 (Div. 2 Only)
Difficulty rating: 1200
Tags: brute force, geometry, implementation

And again a misfortune fell on Poor Student. He is being late for an exam.

Having rushed to a bus stop that is in point (0, 0), he got on a minibus and they drove along a straight line, parallel to axis OX, in the direction of increasing x.

Poor Student knows the following:

- during one run the minibus makes n stops, the i-th stop is in point (xi, 0)
- coordinates of all the stops are different
- the minibus drives at a constant speed, equal to vb
- it can be assumed the passengers get on and off the minibus at a bus stop momentarily
- Student can get off the minibus only at a bus stop
- Student will have to get off the minibus at a terminal stop, if he does not get off earlier
- the University, where the exam will be held, is in point (xu, yu)
- Student can run from a bus stop to the University at a constant speed vs as long as needed
- a distance between two points can be calculated according to the following formula: $$\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}$$
- Student is already on the minibus, so, he cannot get off at the first bus stop

Poor Student wants to get to the University as soon as possible. Help him to choose the bus stop, where he should get off. If such bus stops are multiple, choose the bus stop closest to the University.

Input format:
The first line contains three integer numbers: 2 ≤ n ≤ 100, 1 ≤ vb, vs ≤ 1000. The second line contains n non-negative integers in ascending order: coordinates xi of the bus stop with index i. It is guaranteed that x1 equals to zero, and xn ≤ 105. The third line contains the coordinates of the University, integers xu and yu, not exceeding 105 in absolute value.

Output format:
In the only line output the answer to the problem — index of the optimum bus stop.

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

Note:
As you know, students are a special sort of people, and minibuses usually do not hurry. That's why you should not be surprised, if Student's speed is higher than the speed of the minibus.

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

Example output:
3

Example input:
2 1 1
0 100000
100000 100000

Example output:
2

Editorial:
Hexadecimal's Numbers
Contest: Codeforces Beta Round 9 (Div. 2 Only)
Difficulty rating: 1200
Tags: brute force, implementation, math

One beautiful July morning a terrible thing happened in Mainframe: a mean virus Megabyte somehow got access to the memory of his not less mean sister Hexadecimal. He loaded there a huge amount of n different natural numbers from 1 to n to obtain total control over her energy.

But his plan failed. The reason for this was very simple: Hexadecimal didn't perceive any information, apart from numbers written in binary format. This means that if a number in a decimal representation contained characters apart from 0 and 1, it was not stored in the memory. Now Megabyte wants to know, how many numbers were loaded successfully.

Input format:
Input data contains the only number n (1 ≤ n ≤ 109).

Output format:
Output the only number — answer to the problem.

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

Note:
For n = 10 the answer includes numbers 1 and 10.

Example input:
10

Example output:
2

Editorial:
How many trees?
Contest: Codeforces Beta Round 9 (Div. 2 Only)
Difficulty rating: 1900
Tags: combinatorics, divide and conquer, dp

In one very old text file there was written Great Wisdom. This Wisdom was so Great that nobody could decipher it, even Phong — the oldest among the inhabitants of Mainframe. But still he managed to get some information from there. For example, he managed to learn that User launches games for pleasure — and then terrible Game Cubes fall down on the city, bringing death to those modules, who cannot win the game...

For sure, as guard Bob appeared in Mainframe many modules stopped fearing Game Cubes. Because Bob (as he is alive yet) has never been defeated by User, and he always meddles with Game Cubes, because he is programmed to this.

However, unpleasant situations can happen, when a Game Cube falls down on Lost Angles. Because there lives a nasty virus — Hexadecimal, who is... mmm... very strange. And she likes to play very much. So, willy-nilly, Bob has to play with her first, and then with User.

This time Hexadecimal invented the following entertainment: Bob has to leap over binary search trees with n nodes. We should remind you that a binary search tree is a binary tree, each node has a distinct key, for each node the following is true: the left sub-tree of a node contains only nodes with keys less than the node's key, the right sub-tree of a node contains only nodes with keys greater than the node's key. All the keys are different positive integer numbers from 1 to n. Each node of such a tree can have up to two children, or have no children at all (in the case when a node is a leaf).

In Hexadecimal's game all the trees are different, but the height of each is not lower than h. In this problem «height» stands for the maximum amount of nodes on the way from the root to the remotest leaf, the root node and the leaf itself included. When Bob leaps over a tree, it disappears. Bob gets the access to a Cube, when there are no trees left. He knows how many trees he will have to leap over in the worst case. And you?

Input format:
The input data contains two space-separated positive integer numbers n and h (n ≤ 35, h ≤ n).

Output format:
Output one number — the answer to the problem. It is guaranteed that it does not exceed 9·1018.

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

Example input:
3 2

Example output:
5

Example input:
3 3

Example output:
4

Editorial:
Interesting Graph and Apples
Contest: Codeforces Beta Round 9 (Div. 2 Only)
Difficulty rating: 2300
Tags: dfs and similar, dsu, graphs

Hexadecimal likes drawing. She has drawn many graphs already, both directed and not. Recently she has started to work on a still-life «interesting graph and apples». An undirected graph is called interesting, if each of its vertices belongs to one cycle only — a funny ring — and does not belong to any other cycles. A funny ring is a cycle that goes through all the vertices just once. Moreover, loops are funny rings too.

She has already drawn the apples and some of the graph edges. But now it is not clear, how to connect the rest of the vertices to get an interesting graph as a result. The answer should contain the minimal amount of added edges. And furthermore, the answer should be the lexicographically smallest one. The set of edges (x1, y1), (x2, y2), ..., (xn, yn), where xi ≤ yi, is lexicographically smaller than the set (u1, v1), (u2, v2), ..., (un, vn), where ui ≤ vi, provided that the sequence of integers x1, y1, x2, y2, ..., xn, yn is lexicographically smaller than the sequence u1, v1, u2, v2, ..., un, vn. If you do not cope, Hexadecimal will eat you. ...eat you alive.

Input format:
The first line of the input data contains a pair of integers n and m (1 ≤ n ≤ 50, 0 ≤ m ≤ 2500) — the amount of vertices and edges respectively. The following lines contain pairs of numbers xi and yi (1 ≤ xi, yi ≤ n) — the vertices that are already connected by edges. The initial graph may contain multiple edges and loops.

Output format:
In the first line output «YES» or «NO»: if it is possible or not to construct an interesting graph. If the answer is «YES», in the second line output k — the amount of edges that should be added to the initial graph. Finally, output k lines: pairs of vertices xj and yj, between which edges should be drawn. The result may contain multiple edges and loops. k can be equal to zero.

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

Example input:
3 2
1 2
2 3

Example output:
YES
1
1 3

Editorial:
Kyoya and Photobooks
Contest: Codeforces Round 309 (Div. 2)
Difficulty rating: 900
Tags: brute force, math, strings

Kyoya Ootori is selling photobooks of the Ouran High School Host Club. He has 26 photos, labeled "a" to "z", and he has compiled them into a photo booklet with some photos in some order (possibly with some photos being duplicated). A photo booklet can be described as a string of lowercase letters, consisting of the photos in the booklet in order. He now wants to sell some "special edition" photobooks, each with one extra photo inserted anywhere in the book. He wants to make as many distinct photobooks as possible, so he can make more money. He asks Haruhi, how many distinct photobooks can he make by inserting one extra photo into the photobook he already has?

Please help Haruhi solve this problem.

Input format:
The first line of input will be a single string s (1 ≤ |s| ≤ 20). String s consists only of lowercase English letters.

Output format:
Output a single integer equal to the number of distinct photobooks Kyoya Ootori can make.

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

Note:
In the first case, we can make 'ab','ac',...,'az','ba','ca',...,'za', and 'aa', producing a total of 51 distinct photo booklets.

Example input:
a

Example output:
51

Example input:
hi

Example output:
76

Editorial:
It's enough to just simulate adding every character at every position at the string, and removing any duplicates. For instance, we can use a HashSet of Strings in Java to do this.
Bonus: Prove that the number of ways is always (length of string + 1) * 25 + 1.