1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Fence
Contest: Codeforces Round 145 (Div. 2, ACM-ICPC Rules)
Difficulty rating: 1800
Tags: dp

Vasya should paint a fence in front of his own cottage. The fence is a sequence of n wooden boards arranged in a single row. Each board is a 1 centimeter wide rectangle. Let's number the board fence using numbers 1, 2, ..., n from left to right. The height of the i-th board is hi centimeters.

Vasya has a 1 centimeter wide brush and the paint of two colors, red and green. Of course, the amount of the paint is limited. Vasya counted the area he can paint each of the colors. It turned out that he can not paint over a square centimeters of the fence red, and he can not paint over b square centimeters green. Each board of the fence should be painted exactly one of the two colors. Perhaps Vasya won't need one of the colors.

In addition, Vasya wants his fence to look smart. To do this, he should paint the fence so as to minimize the value that Vasya called the fence unattractiveness value. Vasya believes that two consecutive fence boards, painted different colors, look unattractive. The unattractiveness value of a fence is the total length of contact between the neighboring boards of various colors. To make the fence look nice, you need to minimize the value as low as possible. Your task is to find what is the minimum unattractiveness Vasya can get, if he paints his fence completely.

The picture shows the fence, where the heights of boards (from left to right) are 2,3,2,4,3,1. The first and the fifth boards are painted red, the others are painted green. The first and the second boards have contact length 2, the fourth and fifth boards have contact length 3, the fifth and the sixth have contact length 1. Therefore, the unattractiveness of the given painted fence is 2+3+1=6.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 200) — the number of boards in Vasya's fence.

The second line contains two integers a and b (0 ≤ a, b ≤ 4·104) — the area that can be painted red and the area that can be painted green, correspondingly.

The third line contains a sequence of n integers h1, h2, ..., hn (1 ≤ hi ≤ 200) — the heights of the fence boards.

All numbers in the lines are separated by single spaces.

Output format:
Print a single number — the minimum unattractiveness value Vasya can get if he paints his fence completely. If it is impossible to do, print  - 1.

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

Example input:
4
5 7
3 3 4 1

Example output:
3

Example input:
3
2 3
1 3 1

Example output:
2

Editorial:
Practice
Contest: Codeforces Round 145 (Div. 2, ACM-ICPC Rules)
Difficulty rating: 1600
Tags: constructive algorithms, divide and conquer, implementation

Little time is left before Berland annual football championship. Therefore the coach of team "Losewille Rangers" decided to resume the practice, that were indefinitely interrupted for uncertain reasons. Overall there are n players in "Losewille Rangers". Each player on the team has a number — a unique integer from 1 to n. To prepare for the championship, the coach Mr. Floppe decided to spend some number of practices.

Mr. Floppe spent some long nights of his holiday planning how to conduct the practices. He came to a very complex practice system. Each practice consists of one game, all n players of the team take part in the game. The players are sorted into two teams in some way. In this case, the teams may have different numbers of players, but each team must have at least one player.

The coach wants to be sure that after the series of the practice sessions each pair of players had at least one practice, when they played in different teams. As the players' energy is limited, the coach wants to achieve the goal in the least number of practices.

Help him to schedule the practices.

Input format:
A single input line contains integer n (2 ≤ n ≤ 1000).

Output format:
In the first line print m — the minimum number of practices the coach will have to schedule. Then print the descriptions of the practices in m lines.

In the i-th of those lines print fi — the number of players in the first team during the i-th practice (1 ≤ fi < n), and fi numbers from 1 to n — the numbers of players in the first team. The rest of the players will play in the second team during this practice. Separate numbers on a line with spaces. Print the numbers of the players in any order. If there are multiple optimal solutions, print any of them.

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

Example input:
2

Example output:
1
1 1

Example input:
3

Example output:
2
2 1 2
1 1

Editorial:
Tit for Tat
Contest: Codeforces Round 717 (Div. 2)
Difficulty rating: 800
Tags: greedy

Given an array $$$a$$$ of length $$$n$$$, you can do at most $$$k$$$ operations of the following type on it:

- choose $$$2$$$ different elements in the array, add $$$1$$$ to the first, and subtract $$$1$$$ from the second. However, all the elements of $$$a$$$ have to remain non-negative after this operation.

What is lexicographically the smallest array you can obtain?

An array $$$x$$$ is lexicographically smaller than an array $$$y$$$ if there exists an index $$$i$$$ such that $$$x_i<y_i$$$, and $$$x_j=y_j$$$ for all $$$1 \le j < i$$$. Less formally, at the first index $$$i$$$ in which they differ, $$$x_i<y_i$$$.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 20$$$) – the number of test cases you need to solve.

The first line of each test case contains $$$2$$$ integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 100$$$, $$$1 \le k \le 10000$$$) — the number of elements in the array and the maximum number of operations you can make.

The second line contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{n}$$$ ($$$0 \le a_i \le 100$$$) — the elements of the array $$$a$$$.

Output format:
For each test case, print the lexicographically smallest array you can obtain after at most $$$k$$$ operations.

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

Note:
In the second test case, we start by subtracting $$$1$$$ from the first element and adding $$$1$$$ to the second. Then, we can't get any lexicographically smaller arrays, because we can't make any of the elements negative.

Example input:
2
3 1
3 1 4
2 10
1 0

Example output:
2 1 5 
0 1

Editorial:
AGAGA XOOORRR
Contest: Codeforces Round 717 (Div. 2)
Difficulty rating: 1500
Tags: bitmasks, brute force, dp, greedy

Baby Ehab is known for his love for a certain operation. He has an array $$$a$$$ of length $$$n$$$, and he decided to keep doing the following operation on it:

- he picks $$$2$$$ adjacent elements; he then removes them and places a single integer in their place: their bitwise XOR. Note that the length of the array decreases by one.

Now he asks you if he can make all elements of the array equal. Since babies like to make your life harder, he requires that you leave at least $$$2$$$ elements remaining.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 15$$$) — the number of test cases you need to solve.

The first line of each test case contains an integers $$$n$$$ ($$$2 \le n \le 2000$$$) — the number of elements in the array $$$a$$$.

The second line contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{n}$$$ ($$$0 \le a_i < 2^{30}$$$) — the elements of the array $$$a$$$.

Output format:
If Baby Ehab can make all elements equal while leaving at least $$$2$$$ elements standing, print "YES". Otherwise, print "NO".

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

Note:
In the first sample, he can remove the first $$$2$$$ elements, $$$0$$$ and $$$2$$$, and replace them by $$$0 \oplus 2=2$$$. The array will be $$$[2,2]$$$, so all the elements are equal.

In the second sample, there's no way to make all the elements equal.

Example input:
2
3
0 2 2
4
2 3 1 10

Example output:
YES
NO

Editorial:
Baby Ehab Partitions Again
Contest: Codeforces Round 717 (Div. 2)
Difficulty rating: 1700
Tags: bitmasks, constructive algorithms, dp, math

Baby Ehab was toying around with arrays. He has an array $$$a$$$ of length $$$n$$$. He defines an array to be good if there's no way to partition it into $$$2$$$ subsequences such that the sum of the elements in the first is equal to the sum of the elements in the second. Now he wants to remove the minimum number of elements in $$$a$$$ so that it becomes a good array. Can you help him?

A sequence $$$b$$$ is a subsequence of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deleting some (possibly zero or all) elements. A partitioning of an array is a way to divide it into $$$2$$$ subsequences such that every element belongs to exactly one subsequence, so you must use all the elements, and you can't share any elements.

Input format:
The first line contains an integer $$$n$$$ ($$$2 \le n \le 100$$$) — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{n}$$$ ($$$1 \le a_i \le 2000$$$) — the elements of the array $$$a$$$.

Output format:
The first line should contain the minimum number of elements you need to remove.

The second line should contain the indices of the elements you're removing, separated by spaces.

We can show that an answer always exists. If there are multiple solutions, you can print any.

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

Note:
In the first example, you can partition the array into $$$[6,9]$$$ and $$$[3,12]$$$, so you must remove at least $$$1$$$ element. Removing $$$3$$$ is sufficient.

In the second example, the array is already good, so you don't need to remove any elements.

Example input:
4
6 3 9 12

Example output:
1
2

Example input:
2
1 2

Example output:
0

Editorial:
Cut
Contest: Codeforces Round 717 (Div. 2)
Difficulty rating: 2100
Tags: binary search, data structures, dp, graphs, number theory, two pointers

This time Baby Ehab will only cut and not stick. He starts with a piece of paper with an array $$$a$$$ of length $$$n$$$ written on it, and then he does the following:

- he picks a range $$$(l, r)$$$ and cuts the subsegment $$$a_l, a_{l + 1}, \ldots, a_r$$$ out, removing the rest of the array.
- he then cuts this range into multiple subranges.
- to add a number theory spice to it, he requires that the elements of every subrange must have their product equal to their least common multiple (LCM).

Formally, he partitions the elements of $$$a_l, a_{l + 1}, \ldots, a_r$$$ into contiguous subarrays such that the product of every subarray is equal to its LCM. Now, for $$$q$$$ independent ranges $$$(l, r)$$$, tell Baby Ehab the minimum number of subarrays he needs.

Input format:
The first line contains $$$2$$$ integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 10^5$$$) — the length of the array $$$a$$$ and the number of queries.

The next line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$1 \le a_i \le 10^5$$$) — the elements of the array $$$a$$$.

Each of the next $$$q$$$ lines contains $$$2$$$ integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) — the endpoints of this query's interval.

Output format:
For each query, print its answer on a new line.

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

Note:
The first query asks about the whole array. You can partition it into $$$[2]$$$, $$$[3,10,7]$$$, and $$$[5,14]$$$. The first subrange has product and LCM equal to $$$2$$$. The second has product and LCM equal to $$$210$$$. And the third has product and LCM equal to $$$70$$$. Another possible partitioning is $$$[2,3]$$$, $$$[10,7]$$$, and $$$[5,14]$$$.

The second query asks about the range $$$(2,4)$$$. Its product is equal to its LCM, so you don't need to partition it further.

The last query asks about the range $$$(3,5)$$$. You can partition it into $$$[10,7]$$$ and $$$[5]$$$.

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

Example output:
3
1
2

Editorial:
Baby Ehab Plays with Permutations
Contest: Codeforces Round 717 (Div. 2)
Difficulty rating: 2500
Tags: combinatorics, dp, math

This time around, Baby Ehab will play with permutations. He has $$$n$$$ cubes arranged in a row, with numbers from $$$1$$$ to $$$n$$$ written on them. He'll make exactly $$$j$$$ operations. In each operation, he'll pick up $$$2$$$ cubes and switch their positions.

He's wondering: how many different sequences of cubes can I have at the end? Since Baby Ehab is a turbulent person, he doesn't know how many operations he'll make, so he wants the answer for every possible $$$j$$$ between $$$1$$$ and $$$k$$$.

Input format:
The only line contains $$$2$$$ integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^9$$$, $$$1 \le k \le 200$$$) — the number of cubes Baby Ehab has, and the parameter $$$k$$$ from the statement.

Output format:
Print $$$k$$$ space-separated integers. The $$$i$$$-th of them is the number of possible sequences you can end up with if you do exactly $$$i$$$ operations. Since this number can be very large, print the remainder when it's divided by $$$10^9+7$$$.

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

Note:
In the second example, there are $$$3$$$ sequences he can get after $$$1$$$ swap, because there are $$$3$$$ pairs of cubes he can swap. Also, there are $$$3$$$ sequences he can get after $$$2$$$ swaps:

- $$$[1,2,3]$$$,
- $$$[3,1,2]$$$,
- $$$[2,3,1]$$$.

Example input:
2 3

Example output:
1 1 1

Example input:
3 2

Example output:
3 3

Editorial:
About Bacteria
Contest: Codeforces Round 125 (Div. 1)
Difficulty rating: 1700
Tags: implementation, math

Qwerty the Ranger took up a government job and arrived on planet Mars. He should stay in the secret lab and conduct some experiments on bacteria that have funny and abnormal properties. The job isn't difficult, but the salary is high.

At the beginning of the first experiment there is a single bacterium in the test tube. Every second each bacterium in the test tube divides itself into k bacteria. After that some abnormal effects create b more bacteria in the test tube. Thus, if at the beginning of some second the test tube had x bacteria, then at the end of the second it will have kx + b bacteria.

The experiment showed that after n seconds there were exactly z bacteria and the experiment ended at this point.

For the second experiment Qwerty is going to sterilize the test tube and put there t bacteria. He hasn't started the experiment yet but he already wonders, how many seconds he will need to grow at least z bacteria. The ranger thinks that the bacteria will divide by the same rule as in the first experiment.

Help Qwerty and find the minimum number of seconds needed to get a tube with at least z bacteria in the second experiment.

Input format:
The first line contains four space-separated integers k, b, n and t (1 ≤ k, b, n, t ≤ 106) — the parameters of bacterial growth, the time Qwerty needed to grow z bacteria in the first experiment and the initial number of bacteria in the second experiment, correspondingly.

Output format:
Print a single number — the minimum number of seconds Qwerty needs to grow at least z bacteria in the tube.

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

Example input:
3 1 3 5

Example output:
2

Example input:
1 4 4 7

Example output:
3

Editorial:
Jumping on Walls
Contest: Codeforces Round 125 (Div. 1)
Difficulty rating: 1400
Tags: shortest paths

Vasya plays a computer game with ninjas. At this stage Vasya's ninja should get out of a deep canyon.

The canyon consists of two vertical parallel walls, their height is n meters. Let's imagine that we split these walls into 1 meter-long areas and number them with positive integers from 1 to n from bottom to top. Some areas are safe and the ninja can climb them. Others are spiky and ninja can't be there. Let's call such areas dangerous.

Initially the ninja is on the lower area of the left wall. He can use each second to perform one of the following actions:

- climb one area up;
- climb one area down;
- jump to the opposite wall. That gets the ninja to the area that is exactly k meters higher than the area he jumped from. More formally, if before the jump the ninja is located at area x of one wall, then after the jump he is located at area x + k of the other wall.

If at some point of time the ninja tries to get to an area with a number larger than n, then we can assume that the ninja got out of the canyon.

The canyon gets flooded and each second the water level raises one meter. Initially the water level is at the lower border of the first area. Ninja cannot be on the area covered by water. We can assume that the ninja and the water "move in turns" — first the ninja performs some action, then the water raises for one meter, then the ninja performs one more action and so on.

The level is considered completed if the ninja manages to get out of the canyon.

After several failed attempts Vasya started to doubt whether it is possible to complete the level at all. Help him answer the question.

Input format:
The first line contains two integers n and k (1 ≤ n, k ≤ 105) — the height of the canyon and the height of ninja's jump, correspondingly.

The second line contains the description of the left wall — a string with the length of n characters. The i-th character represents the state of the i-th wall area: character "X" represents a dangerous area and character "-" represents a safe area.

The third line describes the right wall in the same format.

It is guaranteed that the first area of the left wall is not dangerous.

Output format:
Print "YES" (without the quotes) if the ninja can get out from the canyon, otherwise, print "NO" (without the quotes).

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

Note:
In the first sample the ninja should first jump to the right wall, then go one meter down along the right wall, then jump to the left wall. The next jump can get the ninja from the canyon.

In the second sample there's no way the ninja can get out of the canyon.

Example input:
7 3
---X--X
-X--XX-

Example output:
YES

Example input:
6 2
--X-X-
X--XX-

Example output:
NO

Editorial:
Delivering Carcinogen
Contest: Codeforces Round 125 (Div. 1)
Difficulty rating: 2400
Tags: binary search, geometry

Qwerty the Ranger arrived to the Diatar system with a very important task. He should deliver a special carcinogen for scientific research to planet Persephone. This is urgent, so Qwerty has to get to the planet as soon as possible. A lost day may fail negotiations as nobody is going to pay for an overdue carcinogen.

You can consider Qwerty's ship, the planet Persephone and the star Diatar points on a plane. Diatar is located in the origin of coordinate axes — at point (0, 0). Persephone goes round Diatar along a circular orbit with radius R in the counter-clockwise direction at constant linear speed vp (thus, for instance, a full circle around the star takes $$\frac{2\pi R}{v_p}$$ of time). At the initial moment of time Persephone is located at point (xp, yp).

At the initial moment of time Qwerty's ship is at point (x, y). Qwerty can move in any direction at speed of at most v (v > vp). The star Diatar is hot (as all stars), so Qwerty can't get too close to it. The ship's metal sheathing melts at distance r (r < R) from the star.

Find the minimum time Qwerty needs to get the carcinogen to planet Persephone.

Input format:
The first line contains space-separated integers xp, yp and vp ( - 104 ≤ xp, yp ≤ 104, 1 ≤ vp < 104) — Persephone's initial position and the speed at which it goes round Diatar.

The second line contains space-separated integers x, y, v and r ( - 104 ≤ x, y ≤ 104, 1 < v ≤ 104, 1 ≤ r ≤ 104) — The intial position of Qwerty's ship, its maximum speed and the minimum safe distance to star Diatar.

It is guaranteed that r2 < x2 + y2, r2 < xp2 + yp2 and vp < v.

Output format:
Print a single real number — the minimum possible delivery time. The answer will be considered valid if its absolute or relative error does not exceed 10 - 6.

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

Example input:
10 0 1
-10 0 2 8

Example output:
9.584544103

Example input:
50 60 10
50 60 20 40

Example output:
0.000000000

Editorial:
Cube Snake
Contest: Codeforces Round 125 (Div. 1)
Difficulty rating: 2700
Tags: constructive algorithms

You've got an n × n × n cube, split into unit cubes. Your task is to number all unit cubes in this cube with positive integers from 1 to n3 so that:

- each number was used as a cube's number exactly once;
- for each 1 ≤ i < n3, unit cubes with numbers i and i + 1 were neighbouring (that is, shared a side);
- for each 1 ≤ i < n there were at least two different subcubes with sizes i × i × i, made from unit cubes, which are numbered with consecutive numbers. That is, there are such two numbers x and y, that the unit cubes of the first subcube are numbered by numbers x, x + 1, ..., x + i3 - 1, and the unit cubes of the second subcube are numbered by numbers y, y + 1, ..., y + i3 - 1.

Find and print the required numeration of unit cubes of the cube.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 50) — the size of the cube, whose unit cubes need to be numbered.

Output format:
Print all layers of the cube as n n × n matrices. Separate them with new lines. Print the layers in the order in which they follow in the cube. See the samples for clarifications.

It is guaranteed that there always is a solution that meets the conditions given in the problem statement.

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

Note:
In the sample the cubes with sizes 2 × 2 × 2 are numbered with integers 1, ..., 8 and 5, ..., 12.

Example input:
3

Example output:
1 4 17
2 3 18
27 26 19
8 5 16
7 6 15
24 25 20
9 12 13
10 11 14
23 22 21

Editorial: