1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Sum of Digits
Contest: Educational Codeforces Round 90 (Rated for Div. 2)
Difficulty rating: 2200
Tags: brute force, constructive algorithms, dp, greedy

Let $$$f(x)$$$ be the sum of digits of a decimal number $$$x$$$.

Find the smallest non-negative integer $$$x$$$ such that $$$f(x) + f(x + 1) + \dots + f(x + k) = n$$$.

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

Each test case consists of one line containing two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 150$$$, $$$0 \le k \le 9$$$).

Output format:
For each test case, print one integer without leading zeroes. If there is no such $$$x$$$ that $$$f(x) + f(x + 1) + \dots + f(x + k) = n$$$, print $$$-1$$$; otherwise, print the minimum $$$x$$$ meeting that constraint.

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

Example input:
7
1 0
1 1
42 7
13 7
99 1
99 0
99 2

Example output:
1
0
4
-1
599998
99999999999
7997

Editorial:
There are many ways to solve this problem (including precalculating all answers), but the model solution is based on the following:
In most cases, $$$f(x + 1) = f(x) + 1$$$. It is not true only when the last digit of $$$x$$$ is $$$9$$$ (and if we know the number of $$$9$$$-digits at the end of $$$x$$$, we can easily derive the formula for $$$f(x + 1)$$$). And since $$$k \le 9$$$, there will be at most one number with last digit equal to $$$9$$$ in $$$[x, x + 1, \dots, x + k]$$$.
Let's iterate on the last digit of $$$x$$$ and the number of $$$9$$$-digits before it. Suppose the fixed $$$x$$$ has no other digits other than the last one and several $$$9$$$-digits before it. Let's calculate $$$s = f(x) + f(x + 1) + f(x + 2) \dots + f(x + k)$$$.
Here goes the trick. If we prepend $$$x$$$ with several digits such that the last of them is not $$$9$$$, and the sum of those digits is $$$d$$$, then $$$f(x) + f(x + 1) + f(x + 2) \dots + f(x + k) = s + d(k + 1)$$$. So we can easily derive the value of $$$d$$$ we need and construct the smallest number with sum of digits equal to $$$d$$$ (don't forget that the last digit should not be $$$9$$$).
Launch of Collider
Contest: Codeforces Round 363 (Div. 2)
Difficulty rating: 1000
Tags: implementation

There will be a launch of a new, powerful and unusual collider very soon, which located along a straight line. n particles will be launched inside it. All of them are located in a straight line and there can not be two or more particles located in the same point. The coordinates of the particles coincide with the distance in meters from the center of the collider, xi is the coordinate of the i-th particle and its position in the collider at the same time. All coordinates of particle positions are even integers.

You know the direction of each particle movement — it will move to the right or to the left after the collider's launch start. All particles begin to move simultaneously at the time of the collider's launch start. Each particle will move straight to the left or straight to the right with the constant speed of 1 meter per microsecond. The collider is big enough so particles can not leave it in the foreseeable time.

Write the program which finds the moment of the first collision of any two particles of the collider. In other words, find the number of microseconds before the first moment when any two particles are at the same point.

Input format:
The first line contains the positive integer n (1 ≤ n ≤ 200 000) — the number of particles.

The second line contains n symbols "L" and "R". If the i-th symbol equals "L", then the i-th particle will move to the left, otherwise the i-th symbol equals "R" and the i-th particle will move to the right.

The third line contains the sequence of pairwise distinct even integers x1, x2, ..., xn (0 ≤ xi ≤ 109) — the coordinates of particles in the order from the left to the right. It is guaranteed that the coordinates of particles are given in the increasing order.

Output format:
In the first line print the only integer — the first moment (in microseconds) when two particles are at the same point and there will be an explosion.

Print the only integer -1, if the collision of particles doesn't happen.

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

Note:
In the first sample case the first explosion will happen in 1 microsecond because the particles number 1 and 2 will simultaneously be at the same point with the coordinate 3.

In the second sample case there will be no explosion because there are no particles which will simultaneously be at the same point.

Example input:
4
RLRL
2 4 6 10

Example output:
1

Example input:
3
LLR
40 50 60

Example output:
-1

Editorial:
To solve this problem it is enough to look at all pairs of adjacent particles such that the left particle will move to the right and the right particle will move to the left. If there is no such pair the answer is -1. Otherwise, let's iterate through the particles from the left to the right. If the particle i will move to the right and the particle i + 1 will move to the left we know that this particles will be at the same point simultaneously, so we need to update the answer with value (xi + 1 - xi) / 2. The answer is always integer because all coordinates of the particles are even numbers.
One Bomb
Contest: Codeforces Round 363 (Div. 2)
Difficulty rating: 1400
Tags: implementation

You are given a description of a depot. It is a rectangular checkered field of n × m size. Each cell in a field can be empty (".") or it can be occupied by a wall ("*").

You have one bomb. If you lay the bomb at the cell (x, y), then after triggering it will wipe out all walls in the row x and all walls in the column y.

You are to determine if it is possible to wipe out all walls in the depot by placing and triggering exactly one bomb. The bomb can be laid both in an empty cell or in a cell occupied by a wall.

Input format:
The first line contains two positive integers n and m (1 ≤ n, m ≤ 1000) — the number of rows and columns in the depot field.

The next n lines contain m symbols "." and "*" each — the description of the field. j-th symbol in i-th of them stands for cell (i, j). If the symbol is equal to ".", then the corresponding cell is empty, otherwise it equals "*" and the corresponding cell is occupied by a wall.

Output format:
If it is impossible to wipe out all walls by placing and triggering exactly one bomb, then print "NO" in the first line (without quotes).

Otherwise print "YES" (without quotes) in the first line and two integers in the second line — the coordinates of the cell at which the bomb should be laid. If there are multiple answers, print any of them.

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

Example input:
3 4
.*..
....
.*..

Example output:
YES
1 2

Example input:
3 3
..*
.*.
*..

Example output:
NO

Editorial:
To solve this problem we need to calculate two arrays V[] and G[], where V[j] must be equal to the number of walls in the column number j and G[i] must be equal to the number of walls in the row number i. Also let's store the total number of walls in the variable cur.
Now we need to look over the cells. Let the current cell be (x, y). Let's count the value cur — how many walls will destroy the bomb planted in the cell (x, y): cnt = V[y] + G[x]. If the cell (x, y) has a wall we count it twice, so we need to subtract 1 from the cnt. If cur = cnt we found the answer and need to plant the bomb in the cell (x, y).
If there is no such cell we need to print "NO".
Visiting a Friend
Contest: Codeforces Round 453 (Div. 2)
Difficulty rating: 1100
Tags: greedy, implementation

Pig is visiting a friend.

Pig's house is located at point 0, and his friend's house is located at point m on an axis.

Pig can use teleports to move along the axis.

To use a teleport, Pig should come to a certain point (where the teleport is located) and choose where to move: for each teleport there is the rightmost point it can move Pig to, this point is known as the limit of the teleport.

Formally, a teleport located at point x with limit y can move Pig from point x to any point within the segment [x; y], including the bounds.

Determine if Pig can visit the friend using teleports only, or he should use his car.

Input format:
The first line contains two integers n and m (1 ≤ n ≤ 100, 1 ≤ m ≤ 100) — the number of teleports and the location of the friend's house.

The next n lines contain information about teleports.

The i-th of these lines contains two integers ai and bi (0 ≤ ai ≤ bi ≤ m), where ai is the location of the i-th teleport, and bi is its limit.

It is guaranteed that ai ≥ ai - 1 for every i (2 ≤ i ≤ n).

Output format:
Print "YES" if there is a path from Pig's house to his friend's house that uses only teleports, and "NO" otherwise.

You can print each letter in arbitrary case (upper or lower).

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

Note:
The first example is shown on the picture below:

Pig can use the first teleport from his house (point 0) to reach point 2, then using the second teleport go from point 2 to point 3, then using the third teleport go from point 3 to point 5, where his friend lives.

The second example is shown on the picture below:

You can see that there is no path from Pig's house to his friend's house that uses only teleports.

Example input:
3 5
0 2
2 4
3 5

Example output:
YES

Example input:
3 7
0 4
2 5
6 7

Example output:
NO

Editorial:
Note that if we can get to some point x, then we can get to all points <= x. So we can support the rightmost point where we can get to. Then if this point can use the teleport (if this point is to the right of the teleport), we'll try to move it (If the limit of the teleport is to the right of the current point, then move it there). Then in the end we need to check that the rightmost point where we can get is equal to M.
Coloring a Tree
Contest: Codeforces Round 453 (Div. 2)
Difficulty rating: 1200
Tags: dfs and similar, dsu, greedy

You are given a rooted tree with n vertices. The vertices are numbered from 1 to n, the root is the vertex number 1.

Each vertex has a color, let's denote the color of vertex v by cv. Initially cv = 0.

You have to color the tree into the given colors using the smallest possible number of steps. On each step you can choose a vertex v and a color x, and then color all vectices in the subtree of v (including v itself) in color x. In other words, for every vertex u, such that the path from root to u passes through v, set cu = x.

It is guaranteed that you have to color each vertex in a color different from 0.

You can learn what a rooted tree is using the link: https://en.wikipedia.org/wiki/Tree_(graph_theory).

Input format:
The first line contains a single integer n (2 ≤ n ≤ 104) — the number of vertices in the tree.

The second line contains n - 1 integers p2, p3, ..., pn (1 ≤ pi < i), where pi means that there is an edge between vertices i and pi.

The third line contains n integers c1, c2, ..., cn (1 ≤ ci ≤ n), where ci is the color you should color the i-th vertex into.

It is guaranteed that the given graph is a tree.

Output format:
Print a single integer — the minimum number of steps you have to perform to color the tree into given colors.

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

Note:
The tree from the first sample is shown on the picture (numbers are vetices' indices):

On first step we color all vertices in the subtree of vertex 1 into color 2 (numbers are colors):

On seond step we color all vertices in the subtree of vertex 5 into color 1:

On third step we color all vertices in the subtree of vertex 2 into color 1:

The tree from the second sample is shown on the picture (numbers are vetices' indices):

On first step we color all vertices in the subtree of vertex 1 into color 3 (numbers are colors):

On second step we color all vertices in the subtree of vertex 3 into color 1:

On third step we color all vertices in the subtree of vertex 6 into color 2:

On fourth step we color all vertices in the subtree of vertex 4 into color 1:

On fith step we color all vertices in the subtree of vertex 7 into color 3:

Example input:
6
1 2 2 1 5
2 1 1 1 1 1

Example output:
3

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

Example output:
5

Editorial:
Consider the process from the end, we will "delete" any subtree from the tree, whose color of the ancestor of the highest vertex differs from the color of the highest vertex and the colors of all vertices in the subtree are the same. Thus, we can show that the answer is the number of edges whose ends have different colors + 1.
Perfect Triples
Contest: Codeforces Round 633 (Div. 1)
Difficulty rating: 2200
Tags: bitmasks, brute force, constructive algorithms, divide and conquer, math

Consider the infinite sequence $$$s$$$ of positive integers, created by repeating the following steps:

1. Find the lexicographically smallest triple of positive integers $$$(a, b, c)$$$ such that   $$$a \oplus b \oplus c = 0$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.  $$$a$$$, $$$b$$$, $$$c$$$ are not in $$$s$$$.  Here triple of integers $$$(a_1, b_1, c_1)$$$ is considered to be lexicographically smaller than triple $$$(a_2, b_2, c_2)$$$ if sequence $$$[a_1, b_1, c_1]$$$ is lexicographically smaller than sequence $$$[a_2, b_2, c_2]$$$.
2. Append $$$a$$$, $$$b$$$, $$$c$$$ to $$$s$$$ in this order.
3. Go back to the first step.

You have integer $$$n$$$. Find the $$$n$$$-th element of $$$s$$$.

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

A sequence $$$a$$$ is lexicographically smaller than a sequence $$$b$$$ if in the first position where $$$a$$$ and $$$b$$$ differ, the sequence $$$a$$$ has a smaller element than the corresponding element in $$$b$$$.

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

Each of the next $$$t$$$ lines contains a single integer $$$n$$$ ($$$1\le n \le 10^{16}$$$) — the position of the element you want to know.

Output format:
In each of the $$$t$$$ lines, output the answer to the corresponding test case.

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

Note:
The first elements of $$$s$$$ are $$$1, 2, 3, 4, 8, 12, 5, 10, 15, \dots $$$

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

Example output:
1
2
3
4
8
12
5
10
15

Editorial:
Let's try mathematical induction.
First, suppose you have fully used numbers only between $$$1$$$ and $$$4^{n} - 1$$$ inclusive. Now we are going to use all numbers between $$$4^{n}$$$ and $$$4^{n+1} - 1$$$ inclusive by following methods. Following picture is description of $$$a$$$, $$$b$$$ and $$$c$$$ in bitwise manner;
Keep in mind that $$$a$$$, $$$b$$$, and $$$c$$$ are the lexicographically smallest triple, so $$$a \oplus b = c$$$ and $$$a < b < c$$$ should be satisfied at the same time.
Observation 1. $$$a_{2n} = 1$$$, $$$a_{2n+1} = 0$$$, $$$b_{2n} = 0$$$, $$$b_{2n+1} = 1$$$, $$$c_{2n} = c_{2n+1} = 1$$$. Otherwise, $$$a < b < c$$$ condition won't be satisfied, because top two digits of $$$a$$$, $$$b$$$, $$$c$$$ are either $$$01$$$, $$$10$$$, and $$$11$$$.
Then we have more freedom in lower digits, because since the highest $$$2$$$ digits are all different, then we can fill lower digits of three numbers independently. Now look at picture below;
Observation 2. For each $$$2$$$ digits, $$$a$$$, $$$b$$$ and $$$c$$$ should have form like this. Of course, you can use mathematical induction again here; Try to prove this in only $$$2$$$ digits at the first, then expand this lemma to $$$4$$$ digits, $$$6$$$ digits, ..., $$$2n$$$ digits.
Now you know the pattern of digits of $$$a$$$, $$$b$$$, and $$$c$$$. Apply this pattern for each test case. Time complexity is $$$O(\log n)$$$.
Robbery
Contest: Codeforces Beta Round 74 (Div. 1 Only)
Difficulty rating: 1800
Tags: greedy

It is nighttime and Joe the Elusive got into the country's main bank's safe. The safe has n cells positioned in a row, each of them contains some amount of diamonds. Let's make the problem more comfortable to work with and mark the cells with positive numbers from 1 to n from the left to the right.

Unfortunately, Joe didn't switch the last security system off. On the plus side, he knows the way it works.

Every minute the security system calculates the total amount of diamonds for each two adjacent cells (for the cells between whose numbers difference equals 1). As a result of this check we get an n - 1 sums. If at least one of the sums differs from the corresponding sum received during the previous check, then the security system is triggered.

Joe can move the diamonds from one cell to another between the security system's checks. He manages to move them no more than m times between two checks. One of the three following operations is regarded as moving a diamond: moving a diamond from any cell to any other one, moving a diamond from any cell to Joe's pocket, moving a diamond from Joe's pocket to any cell. Initially Joe's pocket is empty, and it can carry an unlimited amount of diamonds. It is considered that before all Joe's actions the system performs at least one check.

In the morning the bank employees will come, which is why Joe has to leave the bank before that moment. Joe has only k minutes left before morning, and on each of these k minutes he can perform no more than m operations. All that remains in Joe's pocket, is considered his loot.

Calculate the largest amount of diamonds Joe can carry with him. Don't forget that the security system shouldn't be triggered (even after Joe leaves the bank) and Joe should leave before morning.

Input format:
The first line contains integers n, m and k (1 ≤ n ≤ 104, 1 ≤ m, k ≤ 109). The next line contains n numbers. The i-th number is equal to the amount of diamonds in the i-th cell — it is an integer from 0 to 105.

Output format:
Print a single number — the maximum number of diamonds Joe can steal.

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

Note:
In the second sample Joe can act like this:

The diamonds' initial positions are 4 1 3.

During the first period of time Joe moves a diamond from the 1-th cell to the 2-th one and a diamond from the 3-th cell to his pocket.

By the end of the first period the diamonds' positions are 3 2 2. The check finds no difference and the security system doesn't go off.

During the second period Joe moves a diamond from the 3-rd cell to the 2-nd one and puts a diamond from the 1-st cell to his pocket.

By the end of the second period the diamonds' positions are 2 3 1. The check finds no difference again and the security system doesn't go off.

Now Joe leaves with 2 diamonds in his pocket.

Example input:
2 3 1
2 3

Example output:
0

Example input:
3 2 2
4 1 3

Example output:
2

Editorial:
Chip Play
Contest: Codeforces Beta Round 74 (Div. 1 Only)
Difficulty rating: 2300
Tags: brute force, data structures, implementation

Let's consider the following game. We have a rectangular field n × m in size. Some squares of the field contain chips.

Each chip has an arrow painted on it. Thus, each chip on the field points in one of the following directions: up, down, left or right.

The player may choose a chip and make a move with it.

The move is the following sequence of actions. The chosen chip is marked as the current one. After that the player checks whether there are more chips in the same row (or in the same column) with the current one that are pointed by the arrow on the current chip. If there is at least one chip then the closest of them is marked as the new current chip and the former current chip is removed from the field. After that the check is repeated. This process can be repeated several times. If a new chip is not found, then the current chip is removed from the field and the player's move ends.

By the end of a move the player receives several points equal to the number of the deleted chips.

By the given initial chip arrangement determine the maximum number of points that a player can receive during one move. Also determine the number of such moves.

Input format:
The first line contains two integers n and m (1 ≤ n, m, n × m ≤ 5000). Then follow n lines containing m characters each — that is the game field description. "." means that this square is empty. "L", "R", "U", "D" mean that this square contains a chip and an arrow on it says left, right, up or down correspondingly.

It is guaranteed that a field has at least one chip.

Output format:
Print two numbers — the maximal number of points a player can get after a move and the number of moves that allow receiving this maximum number of points.

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

Note:
In the first sample the maximum number of points is earned by the chip in the position (3, 3). You can see its progress at the following picture:

All other chips earn fewer points.

Example input:
4 4
DRLD
U.UL
.UUR
RDDL

Example output:
10 1

Example input:
3 5
.D...
RRRLL
.U...

Example output:
6 2

Editorial:
Fire and Ice
Contest: Codeforces Beta Round 74 (Div. 1 Only)
Difficulty rating: 2900
Tags: greedy

The Fire Lord attacked the Frost Kingdom. He has already got to the Ice Fortress, where the Snow Queen dwells. He arranged his army on a segment n in length not far from the city walls. And only the frost magician Solomon can save the Frost Kingdom.

The n-long segment is located at a distance equal exactly to 1 from the castle walls. It can be imaginarily divided into unit segments. On some of the unit segments fire demons are located — no more than one demon per position. Each demon is characterised by his strength - by some positive integer. We can regard the fire demons being idle.

Initially Solomon is positioned on the fortress wall. He can perform the following actions several times in a row:

- "L" — Solomon shifts one unit to the left. This movement cannot be performed on the castle wall.
- "R" — Solomon shifts one unit to the left. This movement cannot be performed if there's no ice block to the right.
- "A" — If there's nothing to the right of Solomon, then Solomon creates an ice block that immediately freezes to the block that Solomon is currently standing on. If there already is an ice block, then Solomon destroys it. At that the ice blocks to the right of the destroyed one can remain but they are left unsupported. Those ice blocks fall down.

Solomon spends exactly a second on each of these actions.

As the result of Solomon's actions, ice blocks' segments fall down. When an ice block falls on a fire demon, the block evaporates and the demon's strength is reduced by 1. When the demons' strength is equal to 0, the fire demon vanishes. The picture below shows how it happens. The ice block that falls on the position with no demon, breaks into lots of tiny pieces and vanishes without hurting anybody.

Help Solomon destroy all the Fire Lord's army in minimum time.

Input format:
The first line contains an integer n (1 ≤ n ≤ 1000). The next line contains n numbers, the i-th of them represents the strength of the fire demon standing of the i-th position, an integer from 1 to 100. If there's no demon on the i-th position, then the i-th number equals to 0. It is guaranteed that the input data have at least one fire demon.

Output format:
Print a string of minimum length, containing characters "L", "R" and "A" — the succession of actions leading to the required result.

If there are several possible answers, print any of them.

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

Example input:
3
1 0 1

Example output:
ARARARALLLA

Example input:
3
0 2 0

Example output:
ARARALAARALA

Editorial:
Mysterious strings
Contest: April Fools Day Contest 2013
Difficulty rating: 1400
Tags: *special, implementation

Input format:
The input contains a single integer a (1 ≤ a ≤ 40).

Output format:
Output a single string.

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

Example input:
2

Example output:
Adams

Example input:
8

Example output:
Van Buren

Editorial:
QR code
Contest: April Fools Day Contest 2013
Difficulty rating: 1500
Tags: *special, implementation

Input format:
The input contains two integers a1, a2 (0 ≤ ai ≤ 32), separated by a single space.

Output format:
Output a single integer.

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

Example input:
1 1

Example output:
0

Example input:
3 7

Example output:
0

Editorial: