1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Bear and Floodlight
Contest: Codeforces Round 226 (Div. 2)
Difficulty rating: 2200
Tags: bitmasks, dp, geometry

One day a bear lived on the Oxy axis. He was afraid of the dark, so he couldn't move at night along the plane points that aren't lit. One day the bear wanted to have a night walk from his house at point (l, 0) to his friend's house at point (r, 0), along the segment of length (r - l). Of course, if he wants to make this walk, he needs each point of the segment to be lit. That's why the bear called his friend (and yes, in the middle of the night) asking for a very delicate favor.

The Oxy axis contains n floodlights. Floodlight i is at point (xi, yi) and can light any angle of the plane as large as ai degree with vertex at point (xi, yi). The bear asked his friend to turn the floodlights so that he (the bear) could go as far away from his house as possible during the walking along the segment. His kind friend agreed to fulfill his request. And while he is at it, the bear wonders: what is the furthest he can go away from his house? Hep him and find this distance.

Consider that the plane has no obstacles and no other light sources besides the floodlights. The bear's friend cannot turn the floodlights during the bear's walk. Assume that after all the floodlights are turned in the correct direction, the bear goes for a walk and his friend goes to bed.

Input format:
The first line contains three space-separated integers n, l, r (1 ≤ n ≤ 20;  - 105 ≤ l ≤ r ≤ 105). The i-th of the next n lines contain three space-separated integers xi, yi, ai ( - 1000 ≤ xi ≤ 1000; 1 ≤ yi ≤ 1000; 1 ≤ ai ≤ 90) — the floodlights' description.

Note that two floodlights can be at the same point of the plane.

Output format:
Print a single real number — the answer to the problem. The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 6.

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

Note:
In the first sample, one of the possible solutions is:

In the second sample, a single solution is:

In the third sample, a single solution is:

Example input:
2 3 5
3 1 45
5 1 45

Example output:
2.000000000

Example input:
1 0 1
1 1 30

Example output:
0.732050808

Editorial:
Bear in the Field
Contest: Codeforces Round 226 (Div. 2)
Difficulty rating: 2300
Tags: math, matrices

Our bear's forest has a checkered field. The checkered field is an n × n table, the rows are numbered from 1 to n from top to bottom, the columns are numbered from 1 to n from left to right. Let's denote a cell of the field on the intersection of row x and column y by record (x, y). Each cell of the field contains growing raspberry, at that, the cell (x, y) of the field contains x + y raspberry bushes.

The bear came out to walk across the field. At the beginning of the walk his speed is (dx, dy). Then the bear spends exactly t seconds on the field. Each second the following takes place:

- Let's suppose that at the current moment the bear is in cell (x, y).
- First the bear eats the raspberry from all the bushes he has in the current cell. After the bear eats the raspberry from k bushes, he increases each component of his speed by k. In other words, if before eating the k bushes of raspberry his speed was (dx, dy), then after eating the berry his speed equals (dx + k, dy + k).
- Let's denote the current speed of the bear (dx, dy) (it was increased after the previous step). Then the bear moves from cell (x, y) to cell (((x + dx - 1) mod n) + 1, ((y + dy - 1) mod n) + 1).
- Then one additional raspberry bush grows in each cell of the field.

You task is to predict the bear's actions. Find the cell he ends up in if he starts from cell (sx, sy). Assume that each bush has infinitely much raspberry and the bear will never eat all of it.

Input format:
The first line of the input contains six space-separated integers: n, sx, sy, dx, dy, t (1 ≤ n ≤ 109; 1 ≤ sx, sy ≤ n;  - 100 ≤ dx, dy ≤ 100; 0 ≤ t ≤ 1018).

Output format:
Print two integers — the coordinates of the cell the bear will end up in after t seconds.

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

Note:
Operation a mod b means taking the remainder after dividing a by b. Note that the result of the operation is always non-negative. For example, ( - 1) mod 3 = 2.

In the first sample before the first move the speed vector will equal (3,4) and the bear will get to cell (4,1). Before the second move the speed vector will equal (9,10) and he bear will get to cell (3,1). Don't forget that at the second move, the number of berry bushes increased by 1.

In the second sample before the first move the speed vector will equal (1,1) and the bear will get to cell (1,1). Before the second move, the speed vector will equal (4,4) and the bear will get to cell (1,1). Don't forget that at the second move, the number of berry bushes increased by 1.

Example input:
5 1 2 0 1 2

Example output:
3 1

Example input:
1 1 1 -1 -1 2

Example output:
1 1

Editorial:
Doremy's Paint 3
Contest: Codeforces Round 906 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms

An array $$$b_1, b_2, \ldots, b_n$$$ of positive integers is good if all the sums of two adjacent elements are equal to the same value. More formally, the array is good if there exists a $$$k$$$ such that $$$b_1 + b_2 = b_2 + b_3 = \ldots = b_{n-1} + b_n = k$$$.

Doremy has an array $$$a$$$ of length $$$n$$$. Now Doremy can permute its elements (change their order) however she wants. Determine if she can make the array good.

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. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 100$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$ n $$$ integers $$$ a_1,a_2,\ldots,a_n $$$ ($$$1 \le a_i \le 10^5$$$).

There are no constraints on the sum of $$$n$$$ over all test cases.

Output format:
For each test case, print "Yes" (without quotes), if it is possible to make the array good, and "No" (without quotes) otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

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

Note:
In the first test case, $$$[8,9]$$$ and $$$[9,8]$$$ are good.

In the second test case, $$$[1,2,1]$$$ is good because $$$a_1+a_2=a_2+a_3=3$$$.

In the third test case, it can be shown that no permutation is good.

Example input:
5
2
8 9
3
1 1 2
4
1 1 4 5
5
2 3 3 3 3
4
100000 100000 100000 100000

Example output:
Yes
Yes
No
No
Yes

Editorial:
Statement says $$$b_1 + b_2 = b_2 + b_3 = \ldots = b_{n-1} + b_n = k$$$. Let's write it as $$$b_i + b_{i+1} = b_{i+1} + b_{i+2}$$$. This is just $$$b_i = b_{i+2}$$$, which means the positions with the same parity should contain same value.
$$$$$$ b_1 = b_3 = b_5 = \cdots \\ b_2 = b_4 = b_6 = \cdots $$$$$$
We know that there are $$$\lceil \frac{n}{2} \rceil$$$ odd numbers and $$$ \lfloor \frac{n}{2}\rfloor$$$ even numbers in $$$[1,n]$$$. Therefore, if and only if we can find $$$\lfloor \frac{n}{2}\rfloor$$$ same numbers, and the remaining are also the same numbers, the answer is YES. All cases can be classified into these categories:
1. All numbers are the same, like $$$[3,3,3,3,3,3]$$$. The answer is YES.
2. There are two different numbers, like $$$[1,2,1,2,1]$$$. The answer is YES if and only if one of the number appears exactly $$$\lfloor \frac{n}{2}\rfloor$$$ times. For example $$$[1,2,1,2,1]$$$ and $$$[2,3,2,3]$$$ are YES while $$$[1,1,1,2]$$$ and $$$[3,3,3,3,4,4]$$$ is NO.
3. There are three or more different numbers, like $$$[1,2,3,2,3]$$$. The answer is NO.
Time complexity $$$O(n)$$$.
Qingshan Loves Strings
Contest: Codeforces Round 906 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, implementation

Qingshan has a string $$$s$$$, while Daniel has a string $$$t$$$. Both strings only contain $$$\texttt{0}$$$ and $$$\texttt{1}$$$.

A string $$$a$$$ of length $$$k$$$ is good if and only if

- $$$a_i \ne a_{i+1}$$$ for all $$$i=1,2,\ldots,k-1$$$.

For example, $$$\texttt{1}$$$, $$$\texttt{101}$$$, $$$\texttt{0101}$$$ are good, while $$$\texttt{11}$$$, $$$\texttt{1001}$$$, $$$\texttt{001100}$$$ are not good.

Qingshan wants to make $$$s$$$ good. To do this, she can do the following operation any number of times (possibly, zero):

- insert $$$t$$$ to any position of $$$s$$$ (getting a new $$$s$$$).

Please tell Qingshan if it is possible to make $$$s$$$ good.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 50$$$) — the length of the strings $$$s$$$ and $$$t$$$, respectively.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$.

The third line of each test case contains a string $$$t$$$ of length $$$m$$$.

It is guaranteed that $$$s$$$ and $$$t$$$ only contain $$$\texttt{0}$$$ and $$$\texttt{1}$$$.

Output format:
For each test case, print "YES" (without quotes), if it is possible to make $$$s$$$ good, and "NO" (without quotes) otherwise.

You can print letters in any case (upper or lower).

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

Note:
In the first test case, $$$s$$$ is good initially, so you can get a good $$$s$$$ by doing zero operations.

In the second test case, you can do the following two operations (the inserted string $$$t$$$ is underlined):

1. $$$\texttt{1}\underline{\texttt{010}}\texttt{11}$$$
2. $$$\texttt{10101}\underline{\texttt{010}}\texttt{1}$$$

and get $$$s = \texttt{101010101}$$$, which is good.

In the third test case, there is no way to make $$$s$$$ good after any number of operations.

Example input:
5
1 1
1
0
3 3
111
010
3 2
111
00
6 7
101100
1010101
10 2
1001001000
10

Example output:
Yes
Yes
No
No
No

Editorial:
There are three circumstances where the answer is "Yes".
1. $$$s$$$ is good initially.
2. $$$t$$$ is good, $$$t=$$$ "10...01", and there is no substring 11 in $$$s$$$.
3. $$$t$$$ is good, $$$t=$$$ "01...10", and there is no substring 00 in $$$s$$$.
Factorise N+M
Contest: Codeforces Round 831 (Div. 1 + Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, number theory

Pak Chanek has a prime number$$$^\dagger$$$ $$$n$$$. Find a prime number $$$m$$$ such that $$$n + m$$$ is not prime.

$$$^\dagger$$$ A prime number is a number with exactly $$$2$$$ factors. The first few prime numbers are $$$2,3,5,7,11,13,\ldots$$$. In particular, $$$1$$$ is not a prime number.

Input format:
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The following lines contain the description of each test case.

The only line of each test case contains a prime number $$$n$$$ ($$$2 \leq n \leq 10^5$$$).

Output format:
For each test case, output a line containing a prime number $$$m$$$ ($$$2 \leq m \leq 10^5$$$) such that $$$n + m$$$ is not prime. It can be proven that under the constraints of the problem, such $$$m$$$ always exists.

If there are multiple solutions, you can output any of them.

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

Note:
In the first test case, $$$m = 2$$$, which is prime, and $$$n + m = 7 + 2 = 9$$$, which is not prime.

In the second test case, $$$m = 7$$$, which is prime, and $$$n + m = 2 + 7 = 9$$$, which is not prime.

In the third test case, $$$m = 47837$$$, which is prime, and $$$n + m = 75619 + 47837 = 123456$$$, which is not prime.

Example input:
3
7
2
75619

Example output:
2
7
47837

Editorial:
There are multiple solutions for this problem. We will discuss two of them.
One solution is to choose $$$m = n$$$. This always guarantees that $$$m$$$ is prime, because $$$n$$$ is always prime. And we can see that $$$n + m = n + n = 2n$$$, which is always not prime, because $$$n > 1$$$ always holds.
Another solution is to choose $$$m=7$$$. If $$$n$$$ is odd, then $$$n+m$$$ will be an even number greater than $$$2$$$ and therefore not prime. Otherwise $$$n$$$ is even. The only even number prime number is $$$2$$$ and it can be verified that $$$2+7=9$$$ is not a prime number.
Time complexity for each test case: $$$O(1)$$$
Card Game
Contest: Codeforces Beta Round 82 (Div. 2)
Difficulty rating: 1000
Tags: implementation

There is a card game called "Durak", which means "Fool" in Russian. The game is quite popular in the countries that used to form USSR. The problem does not state all the game's rules explicitly — you can find them later yourselves if you want.

To play durak you need a pack of 36 cards. Each card has a suit ("S", "H", "D" and "C") and a rank (in the increasing order "6", "7", "8", "9", "T", "J", "Q", "K" and "A"). At the beginning of the game one suit is arbitrarily chosen as trump.

The players move like that: one player puts one or several of his cards on the table and the other one should beat each of them with his cards.

A card beats another one if both cards have similar suits and the first card has a higher rank then the second one. Besides, a trump card can beat any non-trump card whatever the cards’ ranks are. In all other cases you can not beat the second card with the first one.

You are given the trump suit and two different cards. Determine whether the first one beats the second one or not.

Input format:
The first line contains the tramp suit. It is "S", "H", "D" or "C".

The second line contains the description of the two different cards. Each card is described by one word consisting of two symbols. The first symbol stands for the rank ("6", "7", "8", "9", "T", "J", "Q", "K" and "A"), and the second one stands for the suit ("S", "H", "D" and "C").

Output format:
Print "YES" (without the quotes) if the first cards beats the second one. Otherwise, print "NO" (also without the quotes).

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

Example input:
H
QH 9S

Example output:
YES

Example input:
S
8D 6D

Example output:
YES

Editorial:
Choosing Laptop
Contest: Codeforces Beta Round 82 (Div. 2)
Difficulty rating: 1000
Tags: brute force, implementation

Vasya is choosing a laptop. The shop has n laptops to all tastes.

Vasya is interested in the following properties: processor speed, ram and hdd. Vasya is a programmer and not a gamer which is why he is not interested in all other properties.

If all three properties of a laptop are strictly less than those properties of some other laptop, then the first laptop is considered outdated by Vasya. Among all laptops Vasya does not consider outdated, he chooses the cheapest one.

There are very many laptops, which is why Vasya decided to write a program that chooses the suitable laptop. However, Vasya doesn't have his own laptop yet and he asks you to help him.

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

Then follow n lines. Each describes a laptop as speed ram hdd cost. Besides,

- speed, ram, hdd and cost are integers
- 1000 ≤ speed ≤ 4200 is the processor's speed in megahertz
- 256 ≤ ram ≤ 4096 the RAM volume in megabytes
- 1 ≤ hdd ≤ 500 is the HDD in gigabytes
- 100 ≤ cost ≤ 1000 is price in tugriks

All laptops have different prices.

Output format:
Print a single number — the number of a laptop Vasya will choose. The laptops are numbered with positive integers from 1 to n in the order in which they are given in the input data.

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

Note:
In the third sample Vasya considers the first and fifth laptops outdated as all of their properties cannot match those of the third laptop. The fourth one is the cheapest among the laptops that are left. Thus, Vasya chooses the fourth laptop.

Example input:
5
2100 512 150 200
2000 2048 240 350
2300 1024 200 320
2500 2048 80 300
2000 512 180 150

Example output:
4

Editorial:
Buns
Contest: Codeforces Beta Round 82 (Div. 2)
Difficulty rating: 1700
Tags: dp

Lavrenty, a baker, is going to make several buns with stuffings and sell them.

Lavrenty has n grams of dough as well as m different stuffing types. The stuffing types are numerated from 1 to m. Lavrenty knows that he has ai grams left of the i-th stuffing. It takes exactly bi grams of stuffing i and ci grams of dough to cook a bun with the i-th stuffing. Such bun can be sold for di tugriks.

Also he can make buns without stuffings. Each of such buns requires c0 grams of dough and it can be sold for d0 tugriks. So Lavrenty can cook any number of buns with different stuffings or without it unless he runs out of dough and the stuffings. Lavrenty throws away all excess material left after baking.

Find the maximum number of tugriks Lavrenty can earn.

Input format:
The first line contains 4 integers n, m, c0 and d0 (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10, 1 ≤ c0, d0 ≤ 100). Each of the following m lines contains 4 integers. The i-th line contains numbers ai, bi, ci and di (1 ≤ ai, bi, ci, di ≤ 100).

Output format:
Print the only number — the maximum number of tugriks Lavrenty can earn.

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

Note:
To get the maximum number of tugriks in the first sample, you need to cook 2 buns with stuffing 1, 4 buns with stuffing 2 and a bun without any stuffing.

In the second sample Lavrenty should cook 4 buns without stuffings.

Example input:
10 2 2 1
7 3 2 100
12 3 1 10

Example output:
241

Example input:
100 1 25 50
15 5 20 10

Example output:
200

Editorial:
Treasure Island
Contest: Codeforces Beta Round 82 (Div. 2)
Difficulty rating: 1700
Tags: brute force, implementation

Our brave travelers reached an island where pirates had buried treasure. However as the ship was about to moor, the captain found out that some rat ate a piece of the treasure map.

The treasure map can be represented as a rectangle n × m in size. Each cell stands for an islands' square (the square's side length equals to a mile). Some cells stand for the sea and they are impenetrable. All other cells are penetrable (i.e. available) and some of them contain local sights. For example, the large tree on the hills or the cave in the rocks.

Besides, the map also has a set of k instructions. Each instruction is in the following form:

"Walk n miles in the y direction"

The possible directions are: north, south, east, and west. If you follow these instructions carefully (you should fulfill all of them, one by one) then you should reach exactly the place where treasures are buried.

Unfortunately the captain doesn't know the place where to start fulfilling the instructions — as that very piece of the map was lost. But the captain very well remembers that the place contained some local sight. Besides, the captain knows that the whole way goes through the island's penetrable squares.

The captain wants to know which sights are worth checking. He asks you to help him with that.

Input format:
The first line contains two integers n and m (3 ≤ n, m ≤ 1000).

Then follow n lines containing m integers each — the island map's description. "#" stands for the sea. It is guaranteed that all cells along the rectangle's perimeter are the sea. "." stands for a penetrable square without any sights and the sights are marked with uppercase Latin letters from "A" to "Z". Not all alphabet letters can be used. However, it is guaranteed that at least one of them is present on the map. All local sights are marked by different letters.

The next line contains number k (1 ≤ k ≤ 105), after which k lines follow. Each line describes an instruction. Each instruction possesses the form "dir len", where dir stands for the direction and len stands for the length of the way to walk. dir can take values "N", "S", "W" and "E" for North, South, West and East correspondingly. At that, north is to the top, South is to the bottom, west is to the left and east is to the right. len is an integer from 1 to 1000.

Output format:
Print all local sights that satisfy to the instructions as a string without any separators in the alphabetical order. If no sight fits, print "no solution" without the quotes.

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

Example input:
6 10
##########
#K#..#####
#.#..##.##
#..L.#...#
###D###A.#
##########
4
N 2
S 1
E 1
W 2

Example output:
AD

Example input:
3 4
####
#.A#
####
2
W 1
N 2

Example output:
no solution

Editorial:
Space Rescuers
Contest: Codeforces Beta Round 82 (Div. 2)
Difficulty rating: 2100
Tags: geometry, ternary search

The Galaxy contains n planets, there are many different living creatures inhabiting each planet. And each creature can get into troubles! Space rescuers know it perfectly well and they are always ready to help anyone who really needs help. All you need to do is call for them.

Now the space rescuers plan to build the largest in the history of the Galaxy rescue station; however, the rescue station's location is yet to be determined. As some cases are real emergencies, the rescuers want to find such a point in the Galaxy from which it would be possible to get to the remotest planet in the minimum possible time. In other words, the rescuers need such point in the space that the distance between it and the planet remotest from it was minimal (if we compare this point with all other possible points in the space). Unfortunately, the rescuers can't sole this problem.

As the planets are quite remote from each other, they can be considered as points in Euclidean three-dimensional space. The distance between points (xi, yi, zi) and (xj, yj, zj) can be calculated by the formula $$p = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2}$$. The rescue station can be positioned in any point in the space. It can also coincide with some planet.

Galaxy is in danger! Save the space rescuers and find the required point for them.

Input format:
The first line of the input file contains integer n — the number of planets (1 ≤ N ≤ 100). Each of the following n lines contains information about the planets. The i-th line contains three integers xi, yi, zi — the coordinates of the i-th planet ( - 104 ≤ xi, yi, zi ≤ 104, 1 ≤ i ≤ n). No two planets coincide.

Output format:
Print on the first line of the output file three space-separated real numbers x0, y0, z0 — the coordinates for the future base. If there are several solutions, you are allowed to print any of them. The answer will be accepted if the distance from this point to the remotest planet will differ from the juries' variant in no more than 10 - 6 in absolute or relative value.

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

Example input:
5
5 0 0
-5 0 0
0 3 4
4 -3 0
2 2 -2

Example output:
0.000 0.000 0.000

Editorial: