1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Special Numbers
Contest: Codeforces Round 747 (Div. 2)
Difficulty rating: 1100
Tags: bitmasks, math

Theofanis really likes sequences of positive integers, thus his teacher (Yeltsa Kcir) gave him a problem about a sequence that consists of only special numbers.

Let's call a positive number special if it can be written as a sum of different non-negative powers of $$$n$$$. For example, for $$$n = 4$$$ number $$$17$$$ is special, because it can be written as $$$4^0 + 4^2 = 1 + 16 = 17$$$, but $$$9$$$ is not.

Theofanis asks you to help him find the $$$k$$$-th special number if they are sorted in increasing order. Since this number may be too large, output it modulo $$$10^9+7$$$.

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

The first and only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^9$$$; $$$1 \le k \le 10^9$$$).

Output format:
For each test case, print one integer — the $$$k$$$-th special number in increasing order modulo $$$10^9+7$$$.

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

Note:
For $$$n = 3$$$ the sequence is $$$[1,3,4,9...]$$$

Example input:
3
3 4
2 12
105 564

Example output:
9
12
3595374

Editorial:
The problem is the same as finding the $$$k$$$-th number that in base $$$n$$$ has only zeros and ones.
So you can write $$$k$$$ in binary system and instead of powers of $$$2$$$ add powers of $$$n$$$.
Make Them Equal
Contest: Codeforces Round 747 (Div. 2)
Difficulty rating: 1200
Tags: brute force, greedy, math, strings

Theofanis has a string $$$s_1 s_2 \dots s_n$$$ and a character $$$c$$$. He wants to make all characters of the string equal to $$$c$$$ using the minimum number of operations.

In one operation he can choose a number $$$x$$$ ($$$1 \le x \le n$$$) and for every position $$$i$$$, where $$$i$$$ is not divisible by $$$x$$$, replace $$$s_i$$$ with $$$c$$$.

Find the minimum number of operations required to make all the characters equal to $$$c$$$ and the $$$x$$$-s that he should use in his operations.

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 the integer $$$n$$$ ($$$3 \le n \le 3 \cdot 10^5$$$) and a lowercase Latin letter $$$c$$$ — the length of the string $$$s$$$ and the character the resulting string should consist of.

The second line of each test case contains a string $$$s$$$ of lowercase Latin letters — the initial string.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, firstly print one integer $$$m$$$ — the minimum number of operations required to make all the characters equal to $$$c$$$.

Next, print $$$m$$$ integers $$$x_1, x_2, \dots, x_m$$$ ($$$1 \le x_j \le n$$$) — the $$$x$$$-s that should be used in the order they are given.

It can be proved that under given constraints, an answer always exists. If there are multiple answers, print any.

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

Note:
Let's describe what happens in the third test case:

1. $$$x_1 = 2$$$: we choose all positions that are not divisible by $$$2$$$ and replace them, i. e. bzyx $$$\rightarrow$$$ bzbx;
2. $$$x_2 = 3$$$: we choose all positions that are not divisible by $$$3$$$ and replace them, i. e. bzbx $$$\rightarrow$$$ bbbb.

Example input:
3
4 a
aaaa
4 a
baaa
4 b
bzyx

Example output:
0
1
2
2 
2 3

Editorial:
If the whole string is equal to $$$c$$$ then you don't need to make any operations.
In order to find if it is possible with exactly $$$1$$$ operation, we can pass through every $$$x$$$ and count all the letters $$$c$$$ that are divisible by $$$x$$$. This takes $$$O(|s| log |s|)$$$ time complexity.
If for some $$$x$$$ all its multiples are $$$c$$$ then the answer is $$$1$$$ operation with that $$$x$$$.
If all the above conditions don't hold you can always make $$$2$$$ operations and make all the elements equal.
One possible way is with $$$x = |s|$$$ and $$$x = |s|-1$$$.
After the first operation only the last element of $$$s$$$ is not $$$c$$$ thus if we use $$$x = |s|-1$$$ since $$$gcd(|s|,|s|-1) = 1$$$ then $$$|s|$$$ is not divisible by $$$|s|-1$$$ and it will become equal to $$$c$$$.
Time complexity: $$$O(|s| log |s|)$$$ per test case.
Rubik's Cube Coloring (easy version)
Contest: Codeforces Round 747 (Div. 2)
Difficulty rating: 1300
Tags: combinatorics, math

It is the easy version of the problem. The difference is that in this version, there are no nodes with already chosen colors.

Theofanis is starving, and he wants to eat his favorite food, sheftalia. However, he should first finish his homework. Can you help him with this problem?

You have a perfect binary tree of $$$2^k - 1$$$ nodes — a binary tree where all vertices $$$i$$$ from $$$1$$$ to $$$2^{k - 1} - 1$$$ have exactly two children: vertices $$$2i$$$ and $$$2i + 1$$$. Vertices from $$$2^{k - 1}$$$ to $$$2^k - 1$$$ don't have any children. You want to color its vertices with the $$$6$$$ Rubik's cube colors (White, Green, Red, Blue, Orange and Yellow).

Let's call a coloring good when all edges connect nodes with colors that are neighboring sides in the Rubik's cube.

A picture of Rubik's cube and its 2D map.

More formally:

- a white node can not be neighboring with white and yellow nodes;
- a yellow node can not be neighboring with white and yellow nodes;
- a green node can not be neighboring with green and blue nodes;
- a blue node can not be neighboring with green and blue nodes;
- a red node can not be neighboring with red and orange nodes;
- an orange node can not be neighboring with red and orange nodes;

You want to calculate the number of the good colorings of the binary tree. Two colorings are considered different if at least one node is colored with a different color.

The answer may be too large, so output the answer modulo $$$10^9+7$$$.

Input format:
The first and only line contains the integers $$$k$$$ ($$$1 \le k \le 60$$$) — the number of levels in the perfect binary tree you need to color.

Output format:
Print one integer — the number of the different colorings modulo $$$10^9+7$$$.

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

Note:
In the picture below, you can see one of the correct colorings of the first example.

Example input:
3

Example output:
24576

Example input:
14

Example output:
934234

Editorial:
You have $$$6$$$ choices for the first node and $$$4$$$ for each other node. Thus, the answer is $$$6 \cdot 4 ^{2 ^ k - 2}$$$.
Pages
Contest: Codeforces Round 233 (Div. 2)
Tags: implementation

User ainta is making a web site. This time he is going to make a navigation of the pages. In his site, there are n pages numbered by integers from 1 to n. Assume that somebody is on the p-th page now. The navigation will look like this:

<< p - k p - k + 1 ... p - 1 (p) p + 1 ... p + k - 1 p + k >>

When someone clicks the button "<<" he is redirected to page 1, and when someone clicks the button ">>" he is redirected to page n. Of course if someone clicks on a number, he is redirected to the corresponding page.

There are some conditions in the navigation:

- If page 1 is in the navigation, the button "<<" must not be printed.
- If page n is in the navigation, the button ">>" must not be printed.
- If the page number is smaller than 1 or greater than n, it must not be printed.

You can see some examples of the navigations. Make a program that prints the navigation.

Input format:
The first and the only line contains three integers n, p, k (3 ≤ n ≤ 100; 1 ≤ p ≤ n; 1 ≤ k ≤ n)

Output format:
Print the proper navigation. Follow the format of the output from the test samples.

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

Example input:
17 5 2

Example output:
<< 3 4 (5) 6 7 >>

Example input:
6 5 2

Example output:
<< 3 4 (5) 6

Editorial:
Red and Blue Balls
Contest: Codeforces Round 233 (Div. 2)

User ainta has a stack of n red and blue balls. He can apply a certain operation which changes the colors of the balls inside the stack.

- While the top ball inside the stack is red, pop the ball from the top of the stack.
- Then replace the blue ball on the top with a red ball.
- And finally push some blue balls to the stack until the stack has total of n balls inside.

If there are no blue balls inside the stack, ainta can't apply this operation. Given the initial state of the stack, ainta wants to know the maximum number of operations he can repeatedly apply.

Input format:
The first line contains an integer n (1 ≤ n ≤ 50) — the number of balls inside the stack.

The second line contains a string s (|s| = n) describing the initial state of the stack. The i-th character of the string s denotes the color of the i-th ball (we'll number the balls from top to bottom of the stack). If the character is "R", the color is red. If the character is "B", the color is blue.

Output format:
Print the maximum number of operations ainta can repeatedly apply.

Please, do not write 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: 0.5 s
Memory limit: 256.0 MB

Note:
The first example is depicted below.

The explanation how user ainta applies the first operation. He pops out one red ball, changes the color of the ball in the middle from blue to red, and pushes one blue ball.

The explanation how user ainta applies the second operation. He will not pop out red balls, he simply changes the color of the ball on the top from blue to red.

From now on, ainta can't apply any operation because there are no blue balls inside the stack. ainta applied two operations, so the answer is 2.

The second example is depicted below. The blue arrow denotes a single operation.

Example input:
3
RBR

Example output:
2

Example input:
4
RBBR

Example output:
6

Editorial:
Soft Drinking
Contest: Codeforces Round 107 (Div. 2)
Difficulty rating: 800
Tags: implementation, math

This winter is so cold in Nvodsk! A group of n friends decided to buy k bottles of a soft drink called "Take-It-Light" to warm up a bit. Each bottle has l milliliters of the drink. Also they bought c limes and cut each of them into d slices. After that they found p grams of salt.

To make a toast, each friend needs nl milliliters of the drink, a slice of lime and np grams of salt. The friends want to make as many toasts as they can, provided they all drink the same amount. How many toasts can each friend make?

Input format:
The first and only line contains positive integers n, k, l, c, d, p, nl, np, not exceeding 1000 and no less than 1. The numbers are separated by exactly one space.

Output format:
Print a single integer — the number of toasts each friend can make.

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

Note:
A comment to the first sample:

Overall the friends have 4 * 5 = 20 milliliters of the drink, it is enough to make 20 / 3 = 6 toasts. The limes are enough for 10 * 8 = 80 toasts and the salt is enough for 100 / 1 = 100 toasts. However, there are 3 friends in the group, so the answer is min(6, 80, 100) / 3 = 2.

Example input:
3 4 5 10 8 100 3 1

Example output:
2

Example input:
5 100 10 1 19 90 4 3

Example output:
3

Editorial:
Madoka and Strange Thoughts
Contest: Codeforces Round 818 (Div. 2)
Difficulty rating: 800
Tags: math, number theory

Madoka is a very strange girl, and therefore she suddenly wondered how many pairs of integers $$$(a, b)$$$ exist, where $$$1 \leq a, b \leq n$$$, for which $$$\frac{\operatorname{lcm}(a, b)}{\operatorname{gcd}(a, b)} \leq 3$$$.

In this problem, $$$\operatorname{gcd}(a, b)$$$ denotes the greatest common divisor of the numbers $$$a$$$ and $$$b$$$, and $$$\operatorname{lcm}(a, b)$$$ denotes the smallest common multiple of the numbers $$$a$$$ and $$$b$$$.

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

The first and the only line of each test case contains the integer $$$n$$$ ($$$1 \le n \le 10^8$$$).

Output format:
For each test case output a single integer — the number of pairs of integers satisfying the condition.

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

Note:
For $$$n = 1$$$ there is exactly one pair of numbers — $$$(1, 1)$$$ and it fits.

For $$$n = 2$$$, there are only $$$4$$$ pairs — $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$ and they all fit.

For $$$n = 3$$$, all $$$9$$$ pair are suitable, except $$$(2, 3)$$$ and $$$(3, 2)$$$, since their $$$\operatorname{lcm}$$$ is $$$6$$$, and $$$\operatorname{gcd}$$$ is $$$1$$$, which doesn't fit the condition.

Example input:
6
1
2
3
4
5
100000000

Example output:
1
4
7
10
11
266666666

Editorial:
Madoka and Underground Competitions
Contest: Codeforces Round 818 (Div. 2)
Difficulty rating: 1100
Tags: constructive algorithms, implementation

Madoka decided to participate in an underground sports programming competition. And there was exactly one task in it:

A square table of size $$$n \times n$$$, where $$$n$$$ is a multiple of $$$k$$$, is called good if only the characters '.' and 'X' are written in it, as well as in any subtable of size $$$1 \times k$$$ or $$$k \times 1$$$, there is at least one character 'X'. In other words, among any $$$k$$$ consecutive vertical or horizontal cells, there must be at least one containing the character 'X'.

Output any good table that has the minimum possible number of characters 'X', and also the symbol 'X' is written in the cell $$$(r, c)$$$. Rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom, columns are numbered from $$$1$$$ to $$$n$$$ from left to right.

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Description of the test cases follows.

The first and the only line of each test case contains four integers $$$n$$$, $$$k$$$, $$$r$$$, $$$c$$$ ($$$1 \le n \le 500, 1 \le k \le n, 1 \le r, c \le n$$$) — the size of the table, the integer $$$k$$$ and the coordinates of the cell, which must contain the character 'X'. It is guaranteed that $$$n$$$ is a multiple of $$$k$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$500$$$.

Output format:
For each test case, output $$$n$$$ lines, each consisting of $$$n$$$ characters '.' and 'X', — the desired table. If there are several answers, then you can output anyone.

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

Note:
Let's analyze the first test case.

The following tables can be printed as the correct answer:

X....X.X. or ..XX...X.

Note that the following table is invalid because cell $$$(3, 2)$$$ does not contain the character 'X':

X...X...X

In the second test case, the only correct table is:

XXXX

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

Example output:
X..
..X
.X.
XX
XX
.X..X.
X..X..
..X..X
.X..X.
X..X..
..X..X

Editorial:
Madoka and Formal Statement
Contest: Codeforces Round 818 (Div. 2)
Difficulty rating: 1300
Tags: greedy

Given an array of integer $$$a_1, a_2, \ldots, a_n$$$. In one operation you can make $$$a_i := a_i + 1$$$ if $$$i < n$$$ and $$$a_i \leq a_{i + 1}$$$, or $$$i = n$$$ and $$$a_i \leq a_1$$$.

You need to check whether the array $$$a_1, a_2, \ldots, a_n$$$ can become equal to the array $$$b_1, b_2, \ldots, b_n$$$ in some number of operations (possibly, zero). Two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$ are called equal if $$$a_i = b_i$$$ for all integers $$$i$$$ from $$$1$$$ to $$$n$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) – the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) – the elements of the array $$$a$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1, \ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) – the elements of the array $$$b$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output "YES" if you can get the array $$$b$$$, otherwise output "NO".

You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).

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

Note:
In the first test case, the array $$$a$$$ is already equal to the array $$$b$$$.

In the second test case, we can't get the array $$$b$$$, because to do this we need to decrease $$$a_1$$$.

In the fifth test case, we can apply operations in order to the elements with indices $$$4, 3, 3,2,2,2,1,1,1,1$$$, and then get the array $$$[5,5,5,5,5]$$$. After that, you can apply operations in order to elements with indices $$$5,4,4,3,1$$$ and already get an array $$$[6,5,6,7,6]$$$.

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

Example output:
YES
NO
NO
NO
YES

Editorial:
Madoka and The Corruption Scheme
Contest: Codeforces Round 818 (Div. 2)
Difficulty rating: 1900
Tags: combinatorics, constructive algorithms, greedy, math

Madoka decided to entrust the organization of a major computer game tournament "OSU"!

In this tournament, matches are held according to the "Olympic system". In other words, there are $$$2^n$$$ participants in the tournament, numbered with integers from $$$1$$$ to $$$2^n$$$. There are $$$n$$$ rounds in total in the tournament. In the $$$i$$$-th round there are $$$2^{n - i}$$$ matches between two players (one of whom is right, the other is left), after which the winners go further along the tournament grid, and the losing participants are eliminated from the tournament. Herewith, the relative order in the next round does not change. And the winner of the tournament — is the last remaining participant.

But the smaller the participant's number, the more he will pay Madoka if he wins, so Madoka wants the participant with the lowest number to win. To do this, she can arrange the participants in the first round as she likes, and also determine for each match who will win — the participant on the left or right.

But Madoka knows that tournament sponsors can change the winner in matches no more than $$$k$$$ times. (That is, if the participant on the left won before the change, then the participant on the right will win after the change, and if the participant on the right won, then the participant on the left will win after the change).

So, the first image shows the tournament grid that Madoka made, where the red lines denote who should win the match. And the second one shows the tournament grid, after one change in the outcome of the match by sponsors (a match between $$$1$$$ and $$$3$$$ players).

Print the minimum possible number of the winner in the tournament, which Madoka can get regardless of changes in sponsors. But since the answer can be very large, output it modulo $$$10^9 + 7$$$. Note that we need to minimize the answer, and only then take it modulo.

Input format:
The first and the only line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^5, 1 \le k \le \min(2^n - 1, 10^9)$$$) — the number of rounds in the tournament and the number of outcomes that sponsors can change.

Output format:
Print exactly one integer — the minimum number of the winner modulo $$$10^9 + 7$$$

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

Note:
In the first example, there is only one match between players $$$1$$$ and $$$2$$$, so the sponsors can always make player $$$2$$$ wins.

The tournament grid from the second example is shown in the picture in the statement.

Example input:
1 1

Example output:
2

Example input:
2 1

Example output:
3

Editorial:
Madoka and The Best University
Contest: Codeforces Round 818 (Div. 2)
Difficulty rating: 2200
Tags: math, number theory

Madoka wants to enter to "Novosibirsk State University", but in the entrance exam she came across a very difficult task:

Given an integer $$$n$$$, it is required to calculate $$$\sum{\operatorname{lcm}(c, \gcd(a, b))}$$$, for all triples of positive integers $$$(a, b, c)$$$, where $$$a + b + c = n$$$.

In this problem $$$\gcd(x, y)$$$ denotes the greatest common divisor of $$$x$$$ and $$$y$$$, and $$$\operatorname{lcm}(x, y)$$$ denotes the least common multiple of $$$x$$$ and $$$y$$$.

Solve this problem for Madoka and help her to enter to the best university!

Input format:
The first and the only line contains a single integer $$$n$$$ ($$$3 \le n \le 10^5$$$).

Output format:
Print exactly one interger — $$$\sum{\operatorname{lcm}(c, \gcd(a, b))}$$$. Since the answer can be very large, then output it modulo $$$10^9 + 7$$$.

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

Note:
In the first example, there is only one suitable triple $$$(1, 1, 1)$$$. So the answer is $$$\operatorname{lcm}(1, \gcd(1, 1)) = \operatorname{lcm}(1, 1) = 1$$$.

In the second example, $$$\operatorname{lcm}(1, \gcd(3, 1)) + \operatorname{lcm}(1, \gcd(2, 2)) + \operatorname{lcm}(1, \gcd(1, 3)) + \operatorname{lcm}(2, \gcd(2, 1)) + \operatorname{lcm}(2, \gcd(1, 2)) + \operatorname{lcm}(3, \gcd(1, 1)) = \operatorname{lcm}(1, 1) + \operatorname{lcm}(1, 2) + \operatorname{lcm}(1, 1) + \operatorname{lcm}(2, 1) + \operatorname{lcm}(2, 1) + \operatorname{lcm}(3, 1) = 1 + 2 + 1 + 2 + 2 + 3 = 11$$$

Example input:
3

Example output:
1

Example input:
5

Example output:
11

Editorial:
Garden
Contest: Educational Codeforces Round 36 (Rated for Div. 2)
Difficulty rating: 900
Tags: implementation

Luba thinks about watering her garden. The garden can be represented as a segment of length k. Luba has got n buckets, the i-th bucket allows her to water some continuous subsegment of garden of length exactly ai each hour. Luba can't water any parts of the garden that were already watered, also she can't water the ground outside the garden.

Luba has to choose one of the buckets in order to water the garden as fast as possible (as mentioned above, each hour she will water some continuous subsegment of length ai if she chooses the i-th bucket). Help her to determine the minimum number of hours she has to spend watering the garden. It is guaranteed that Luba can always choose a bucket so it is possible water the garden.

See the examples for better understanding.

Input format:
The first line of input contains two integer numbers n and k (1 ≤ n, k ≤ 100) — the number of buckets and the length of the garden, respectively.

The second line of input contains n integer numbers ai (1 ≤ ai ≤ 100) — the length of the segment that can be watered by the i-th bucket in one hour.

It is guaranteed that there is at least one bucket such that it is possible to water the garden in integer number of hours using only this bucket.

Output format:
Print one integer number — the minimum number of hours required to water the garden.

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

Note:
In the first test the best option is to choose the bucket that allows to water the segment of length 3. We can't choose the bucket that allows to water the segment of length 5 because then we can't water the whole garden.

In the second test we can choose only the bucket that allows us to water the segment of length 1.

Example input:
3 6
2 3 5

Example output:
2

Example input:
6 7
1 2 3 4 5 6

Example output:
7

Editorial:
In this problem we just need to find maximum divisor of k that belongs to array a. Let's call it r. Then we need to print $$\frac{\lambda}{T}$$.