1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Obtain The String
Contest: Educational Codeforces Round 81 (Rated for Div. 2)
Difficulty rating: 1600
Tags: dp, greedy, strings

You are given two strings $$$s$$$ and $$$t$$$ consisting of lowercase Latin letters. Also you have a string $$$z$$$ which is initially empty. You want string $$$z$$$ to be equal to string $$$t$$$. You can perform the following operation to achieve this: append any subsequence of $$$s$$$ at the end of string $$$z$$$. A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, if $$$z = ac$$$, $$$s = abcde$$$, you may turn $$$z$$$ into following strings in one operation:

1. $$$z = acace$$$ (if we choose subsequence $$$ace$$$);
2. $$$z = acbcd$$$ (if we choose subsequence $$$bcd$$$);
3. $$$z = acbce$$$ (if we choose subsequence $$$bce$$$).

Note that after this operation string $$$s$$$ doesn't change.

Calculate the minimum number of such operations to turn string $$$z$$$ into string $$$t$$$.

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

The first line of each testcase contains one string $$$s$$$ ($$$1 \le |s| \le 10^5$$$) consisting of lowercase Latin letters.

The second line of each testcase contains one string $$$t$$$ ($$$1 \le |t| \le 10^5$$$) consisting of lowercase Latin letters.

It is guaranteed that the total length of all strings $$$s$$$ and $$$t$$$ in the input does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each testcase, print one integer — the minimum number of operations to turn string $$$z$$$ into string $$$t$$$. If it's impossible print $$$-1$$$.

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

Example input:
3
aabce
ace
abacaba
aax
ty
yyt

Example output:
1
-1
3

Editorial:
The answer is $$$-1$$$ when in string $$$t$$$ there is a character that is not in string $$$s$$$.
Otherwise let's precalculate the following array $$$nxt_{i, j}$$$ = minimum index $$$x$$$ from $$$i$$$ to $$$|s|$$$ such that $$$s_x = j$$$ (if there is no such index then $$$nxt_{i, j} = inf$$$).
Now we can solve this problem by simple greed. Presume that now $$$z = t_0 t_1 \dots t_{i-1}$$$, and last taken symbol in $$$s$$$ is $$$s_{pos}$$$. Then there are two options:
1. if $$$nxt_{pos, i} \neq inf$$$, then $$$i = i + 1$$$, $$$pos = nxt_{pos+1, i}$$$;
2. if $$$nxt_{pos, i} = inf$$$, then $$$pos = 0$$$ and $$$ans = ans + 1$$$ ($$$ans$$$ is equal to $$$0$$$ initially);
Same GCDs
Contest: Educational Codeforces Round 81 (Rated for Div. 2)
Difficulty rating: 1800
Tags: math, number theory

You are given two integers $$$a$$$ and $$$m$$$. Calculate the number of integers $$$x$$$ such that $$$0 \le x < m$$$ and $$$\gcd(a, m) = \gcd(a + x, m)$$$.

Note: $$$\gcd(a, b)$$$ is the greatest common divisor of $$$a$$$ and $$$b$$$.

Input format:
The first line contains the single integer $$$T$$$ ($$$1 \le T \le 50$$$) — the number of test cases.

Next $$$T$$$ lines contain test cases — one per line. Each line contains two integers $$$a$$$ and $$$m$$$ ($$$1 \le a < m \le 10^{10}$$$).

Output format:
Print $$$T$$$ integers — one per test case. For each test case print the number of appropriate $$$x$$$-s.

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

Note:
In the first test case appropriate $$$x$$$-s are $$$[0, 1, 3, 4, 6, 7]$$$.

In the second test case the only appropriate $$$x$$$ is $$$0$$$.

Example input:
3
4 9
5 10
42 9999999967

Example output:
6
1
9999999966

Editorial:
The Euclidean algorithm is based on the next fact: if $$$a \ge b$$$ then $$$\gcd(a, b) = \gcd(a - b, b)$$$. So, if $$$(a + x) \ge m$$$ then $$$\gcd(a + x, m) = \gcd(a + x - m, m)$$$. So we can declare that we are looking at $$$m$$$ different integers $$$x' = (a + x) \mod m$$$ with $$$0 \le x' < m$$$, so all $$$x'$$$ forms a segment $$$[0, m - 1]$$$. So, we need to find the number of $$$x'$$$ ($$$0 \le x' < m$$$) such that $$$\gcd(x', m) = \gcd(a, m)$$$.
Let's denote $$$g = \gcd(a, m)$$$, then $$$a = ga'$$$ and $$$m = gm'$$$. So, $$$\gcd(a, m) = \gcd(ga', gm') = g \cdot \gcd(a', m') = g$$$ or $$$\gcd(a', m') = 1$$$. Since $$$\gcd(x', m) = \gcd(a, m) = g$$$ so we also can represent $$$x' = x^{"}g$$$ and, therefore $$$gcd(x^{"}, m') = 1$$$.
Since $$$0 \le x' < m$$$, then $$$0 \le x^{"} < m'$$$ or we need to calaculate the number of $$$x^{"}$$$ ($$$0 \le x^{"} < m'$$$) such that $$$\gcd(x^{"}, m') = 1$$$. Since $$$gcd(0, m') = m' > 1$$$ so we can consider $$$x^{"} \in [1, m' - 1]$$$ and this is the definition of Euler's totient function $$$\varphi(m')$$$ which is the answer.
Euler's totient function $$$\varphi(m')$$$ can be calculated using factorization of $$$m' = \prod\limits_{i=1}^{l}{p_i^{a_i}}$$$. Then $$$\varphi(m') = m' \prod\limits_{i=1}^{l}{(1 - \frac{1}{p_i})}$$$.
Find Color
Contest: Codeforces Beta Round 39
Difficulty rating: 1300
Tags: constructive algorithms, geometry, implementation, math

Not so long ago as a result of combat operations the main Berland place of interest — the magic clock — was damaged. The cannon's balls made several holes in the clock, that's why the residents are concerned about the repair. The magic clock can be represented as an infinite Cartesian plane, where the origin corresponds to the clock center. The clock was painted two colors as is shown in the picture:

The picture shows only the central part of the clock. This coloring naturally extends to infinity.

The balls can be taken to be points on the plane. Your task is to find the color of the area, damaged by the given ball.

All the points located on the border of one of the areas have to be considered painted black.

Input format:
The first and single line contains two integers x and y — the coordinates of the hole made in the clock by the ball. Each of the numbers x and y has an absolute value that does not exceed 1000.

Output format:
Find the required color.

All the points between which and the origin of coordinates the distance is integral-value are painted black.

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

Example input:
-2 1

Example output:
white

Example input:
2 1

Example output:
black

Editorial:
Repaintings
Contest: Codeforces Beta Round 39
Difficulty rating: 1600
Tags: math

A chessboard n × m in size is given. During the zero minute we repaint all the black squares to the 0 color. During the i-th minute we repaint to the i color the initially black squares that have exactly four corner-adjacent squares painted i - 1 (all such squares are repainted simultaneously). This process continues ad infinitum. You have to figure out how many squares we repainted exactly x times.

The upper left square of the board has to be assumed to be always black. Two squares are called corner-adjacent, if they have exactly one common point.

Input format:
The first line contains integers n and m (1 ≤ n, m ≤ 5000). The second line contains integer x (1 ≤ x ≤ 109).

Output format:
Print how many squares will be painted exactly x times.

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

Example input:
3 3
1

Example output:
4

Example input:
3 3
2

Example output:
1

Editorial:
Berland Square
Contest: Codeforces Beta Round 39
Difficulty rating: 2300
Tags: implementation, math

Last year the world's largest square was built in Berland. It is known that the square can be represented as an infinite plane with an introduced Cartesian system of coordinates. On that square two sets of concentric circles were painted. Let's call the set of concentric circles with radii 1, 2, ..., K and the center in the point (z, 0) a (K, z)-set. Thus, on the square were painted a (N, x)-set and a (M, y)-set. You have to find out how many parts those sets divided the square into.

Input format:
The first line contains integers N, x, M, y. (1 ≤ N, M ≤ 100000,  - 100000 ≤ x, y ≤ 100000, x ≠ y).

Output format:
Print the sought number of parts.

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

Note:
Picture for the third sample:

Example input:
1 0 1 1

Example output:
4

Example input:
1 0 1 2

Example output:
3

Editorial:
Interesting Sequence
Contest: Codeforces Beta Round 39
Difficulty rating: 2600
Tags: math

Berland scientists noticed long ago that the world around them depends on Berland population. Due to persistent research in this area the scientists managed to find out that the Berland chronology starts from the moment when the first two people came to that land (it is considered to have happened in the first year). After one Berland year after the start of the chronology the population had already equaled 13 people (the second year). However, tracing the population number during the following years was an ultimately difficult task, still it was found out that if di — the number of people in Berland in the year of i, then either di = 12di - 2, or di = 13di - 1 - 12di - 2. Of course no one knows how many people are living in Berland at the moment, but now we can tell if there could possibly be a year in which the country population equaled A. That's what we ask you to determine. Also, if possible, you have to find out in which years it could be (from the beginning of Berland chronology). Let's suppose that it could be in the years of a1, a2, ..., ak. Then you have to define how many residents could be in the country during those years apart from the A variant. Look at the examples for further explanation.

Input format:
The first line contains integer A (1 ≤ A < 10300). It is guaranteed that the number doesn't contain leading zeros.

Output format:
On the first output line print YES, if there could be a year in which the total population of the country equaled A, otherwise print NO.

If the answer is YES, then you also have to print number k — the number of years in which the population could equal A. On the next line you have to output precisely k space-separated numbers — a1, a2, ..., ak. Those numbers have to be output in the increasing order.

On the next line you should output number p — how many variants of the number of people could be in the years of a1, a2, ..., ak, apart from the A variant. On each of the next p lines you have to print one number — the sought number of residents. Those number also have to go in the increasing order.

If any number (or both of them) k or p exceeds 1000, then you have to print 1000 instead of it and only the first 1000 possible answers in the increasing order.

The numbers should have no leading zeros.

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

Example input:
2

Example output:
YES
1
1
0

Example input:
3

Example output:
NO

Editorial:
Number Table
Contest: Codeforces Beta Round 39
Difficulty rating: 2500
Tags: combinatorics

As it has been found out recently, all the Berland's current economical state can be described using a simple table n × m in size. n — the number of days in each Berland month, m — the number of months. Thus, a table cell corresponds to a day and a month of the Berland's year. Each cell will contain either 1, or -1, which means the state's gains in a particular month, on a particular day. 1 corresponds to profits, -1 corresponds to losses. It turned out important for successful development to analyze the data on the state of the economy of the previous year, however when the treasurers referred to the archives to retrieve the data, it turned out that the table had been substantially damaged. In some table cells the number values had faded and were impossible to be deciphered. It is known that the number of cells in which the data had been preserved is strictly less than max(n, m). However, there is additional information — the product of the numbers in each line and column equaled -1. Your task is to find out how many different tables may conform to the preserved data. As the answer to the task can be quite large, you have to find it modulo p.

Input format:
The first line contains integers n and m (1 ≤ n, m ≤ 1000). The second line contains the integer k (0 ≤ k < max(n, m)) — the number of cells in which the data had been preserved. The next k lines contain the data on the state of the table in the preserved cells. Each line is of the form "a b c", where a (1 ≤ a ≤ n) — the number of the table row, b (1 ≤ b ≤ m) — the number of the column, c — the value containing in the cell (1 or -1). They are numbered starting from 1. It is guaranteed that no two lines with same a and b values exist. The last line contains an integer p (2 ≤ p ≤ 109 + 7).

Output format:
Print the number of different tables that could conform to the preserved data modulo p.

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

Example input:
2 2
0
100

Example output:
2

Example input:
2 2
1
1 1 -1
100

Example output:
1

Editorial:
Shortest path of the king
Contest: Codeforces Beta Round 3
Difficulty rating: 1000
Tags: greedy, shortest paths

The king is left alone on the chessboard. In spite of this loneliness, he doesn't lose heart, because he has business of national importance. For example, he has to pay an official visit to square t. As the king is not in habit of wasting his time, he wants to get from his current position s to square t in the least number of moves. Help him to do this.

In one move the king can get to the square that has a common side or a common vertex with the square the king is currently in (generally there are 8 different squares he can move to).

Input format:
The first line contains the chessboard coordinates of square s, the second line — of square t.

Chessboard coordinates consist of two characters, the first one is a lowercase Latin letter (from a to h), the second one is a digit from 1 to 8.

Output format:
In the first line print n — minimum number of the king's moves. Then in n lines print the moves themselves. Each move is described with one of the 8: L, R, U, D, LU, LD, RU or RD.

L, R, U, D stand respectively for moves left, right, up and down (according to the picture), and 2-letter combinations stand for diagonal moves. If the answer is not unique, print any of them.

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

Example input:
a8
h1

Example output:
7
RD
RD
RD
RD
RD
RD
RD

Editorial:
Lorry
Contest: Codeforces Beta Round 3
Difficulty rating: 1900
Tags: greedy, sortings

A group of tourists is going to kayak and catamaran tour. A rented lorry has arrived to the boat depot to take kayaks and catamarans to the point of departure. It's known that all kayaks are of the same size (and each of them occupies the space of 1 cubic metre), and all catamarans are of the same size, but two times bigger than kayaks (and occupy the space of 2 cubic metres).

Each waterborne vehicle has a particular carrying capacity, and it should be noted that waterborne vehicles that look the same can have different carrying capacities. Knowing the truck body volume and the list of waterborne vehicles in the boat depot (for each one its type and carrying capacity are known), find out such set of vehicles that can be taken in the lorry, and that has the maximum total carrying capacity. The truck body volume of the lorry can be used effectively, that is to say you can always put into the lorry a waterborne vehicle that occupies the space not exceeding the free space left in the truck body.

Input format:
The first line contains a pair of integer numbers n and v (1 ≤ n ≤ 105; 1 ≤ v ≤ 109), where n is the number of waterborne vehicles in the boat depot, and v is the truck body volume of the lorry in cubic metres. The following n lines contain the information about the waterborne vehicles, that is a pair of numbers ti, pi (1 ≤ ti ≤ 2; 1 ≤ pi ≤ 104), where ti is the vehicle type (1 – a kayak, 2 – a catamaran), and pi is its carrying capacity. The waterborne vehicles are enumerated in order of their appearance in the input file.

Output format:
In the first line print the maximum possible carrying capacity of the set. In the second line print a string consisting of the numbers of the vehicles that make the optimal set. If the answer is not unique, print any of them.

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

Example input:
3 2
1 2
2 7
1 3

Example output:
7
2

Editorial:
Tic-tac-toe
Contest: Codeforces Beta Round 3
Difficulty rating: 1800
Tags: brute force, games, implementation

Certainly, everyone is familiar with tic-tac-toe game. The rules are very simple indeed. Two players take turns marking the cells in a 3 × 3 grid (one player always draws crosses, the other — noughts). The player who succeeds first in placing three of his marks in a horizontal, vertical or diagonal line wins, and the game is finished. The player who draws crosses goes first. If the grid is filled, but neither Xs, nor 0s form the required line, a draw is announced.

You are given a 3 × 3 grid, each grid cell is empty, or occupied by a cross or a nought. You have to find the player (first or second), whose turn is next, or print one of the verdicts below:

- illegal — if the given board layout can't appear during a valid game;
- the first player won — if in the given board layout the first player has just won;
- the second player won — if in the given board layout the second player has just won;
- draw — if the given board layout has just let to a draw.

Input format:
The input consists of three lines, each of the lines contains characters ".", "X" or "0" (a period, a capital letter X, or a digit zero).

Output format:
Print one of the six verdicts: first, second, illegal, the first player won, the second player won or draw.

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

Example input:
X0X
.0.
.X.

Example output:
second

Editorial:
Least Cost Bracket Sequence
Contest: Codeforces Beta Round 3
Difficulty rating: 2600
Tags: greedy

This is yet another problem on regular bracket sequences.

A bracket sequence is called regular, if by inserting "+" and "1" into it we get a correct mathematical expression. For example, sequences "(())()", "()" and "(()(()))" are regular, while ")(", "(()" and "(()))(" are not. You have a pattern of a bracket sequence that consists of characters "(", ")" and "?". You have to replace each character "?" with a bracket so, that you get a regular bracket sequence.

For each character "?" the cost of its replacement with "(" and ")" is given. Among all the possible variants your should choose the cheapest.

Input format:
The first line contains a non-empty pattern of even length, consisting of characters "(", ")" and "?". Its length doesn't exceed 5·104. Then there follow m lines, where m is the number of characters "?" in the pattern. Each line contains two integer numbers ai and bi (1 ≤ ai,  bi ≤ 106), where ai is the cost of replacing the i-th character "?" with an opening bracket, and bi — with a closing one.

Output format:
Print the cost of the optimal regular bracket sequence in the first line, and the required sequence in the second.

Print -1, if there is no answer. If the answer is not unique, print any of them.

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

Example input:
(??)
1 2
2 8

Example output:
4
()()

Editorial:
Buying A House
Contest: Codeforces Round 408 (Div. 2)
Difficulty rating: 800
Tags: brute force, implementation

Zane the wizard had never loved anyone before, until he fell in love with a girl, whose name remains unknown to us.

The girl lives in house m of a village. There are n houses in that village, lining in a straight line from left to right: house 1, house 2, ..., house n. The village is also well-structured: house i and house i + 1 (1 ≤ i < n) are exactly 10 meters away. In this village, some houses are occupied, and some are not. Indeed, unoccupied houses can be purchased.

You will be given n integers a1, a2, ..., an that denote the availability and the prices of the houses. If house i is occupied, and therefore cannot be bought, then ai equals 0. Otherwise, house i can be bought, and ai represents the money required to buy it, in dollars.

As Zane has only k dollars to spare, it becomes a challenge for him to choose the house to purchase, so that he could live as near as possible to his crush. Help Zane determine the minimum distance from his crush's house to some house he can afford, to help him succeed in his love.

Input format:
The first line contains three integers n, m, and k (2 ≤ n ≤ 100, 1 ≤ m ≤ n, 1 ≤ k ≤ 100) — the number of houses in the village, the house where the girl lives, and the amount of money Zane has (in dollars), respectively.

The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 100) — denoting the availability and the prices of the houses.

It is guaranteed that am = 0 and that it is possible to purchase some house with no more than k dollars.

Output format:
Print one integer — the minimum distance, in meters, from the house where the girl Zane likes lives to the house Zane can buy.

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

Note:
In the first sample, with k = 20 dollars, Zane can buy only house 5. The distance from house m = 1 to house 5 is 10 + 10 + 10 + 10 = 40 meters.

In the second sample, Zane can buy houses 6 and 7. It is better to buy house 6 than house 7, since house m = 3 and house 6 are only 30 meters away, while house m = 3 and house 7 are 40 meters away.

Example input:
5 1 20
0 27 32 21 19

Example output:
40

Example input:
7 3 50
62 0 0 0 99 33 22

Example output:
30

Editorial:
This is a simple implementation problem.
Let the ans be infinity initially.
Iterate through the houses. Suppose we are considering house i, update the ans if and only if
1) ai ≠ 0,
2) ai ≤ k, and
3) |i - m| < ans.
The answer is 10 * ans.
This solution runs in O(n).
Curriculum Vitae
Contest: Educational Codeforces Round 28
Difficulty rating: 1500
Tags: brute force, implementation

Hideo Kojima has just quit his job at Konami. Now he is going to find a new place to work. Despite being such a well-known person, he still needs a CV to apply for a job.

During all his career Hideo has produced n games. Some of them were successful, some were not. Hideo wants to remove several of them (possibly zero) from his CV to make a better impression on employers. As a result there should be no unsuccessful game which comes right after successful one in his CV.

More formally, you are given an array s1, s2, ..., sn of zeros and ones. Zero corresponds to an unsuccessful game, one — to a successful one. Games are given in order they were produced, and Hideo can't swap these values. He should remove some elements from this array in such a way that no zero comes right after one.

Besides that, Hideo still wants to mention as much games in his CV as possible. Help this genius of a man determine the maximum number of games he can leave in his CV.

Input format:
The first line contains one integer number n (1 ≤ n ≤ 100).

The second line contains n space-separated integer numbers s1, s2, ..., sn (0 ≤ si ≤ 1). 0 corresponds to an unsuccessful game, 1 — to a successful one.

Output format:
Print one integer — the maximum number of games Hideo can leave in his CV so that no unsuccessful game comes after a successful one.

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

Example input:
4
1 1 0 1

Example output:
3

Example input:
6
0 1 0 0 1 0

Example output:
4

Editorial:
The statement literally asks for the longest subsequence which looks like [0, 0, 0, ..., 1, 1, 1]. Let's find out how many zeroes will be in this sequence and then take all ones which come after the last zero. On each step take the next zero from the beginning of the sequence and count ones after it. Update answer with the maximum value.
You can precalc number of ones on suffix with partial sums but it was not necessary in this task.
Overall complexity: O(n2) (naively) or O(n) (with partial sums).