1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Tablecity
Contest: Bubble Cup 8 - Finals [Online Mirror]
Difficulty rating: 1700
Tags: constructive algorithms, implementation

There was a big bank robbery in Tablecity. In order to catch the thief, the President called none other than Albert – Tablecity’s Chief of Police. Albert does not know where the thief is located, but he does know how he moves.

Tablecity can be represented as 1000 × 2 grid, where every cell represents one district. Each district has its own unique name “(X, Y)”, where X and Y are the coordinates of the district in the grid. The thief’s movement is as

Every hour the thief will leave the district (X, Y) he is currently hiding in, and move to one of the districts: (X - 1, Y), (X + 1, Y), (X - 1, Y - 1), (X - 1, Y + 1), (X + 1, Y - 1), (X + 1, Y + 1) as long as it exists in Tablecity.

Below is an example of thief’s possible movements if he is located in district (7,1):

Albert has enough people so that every hour he can pick any two districts in Tablecity and fully investigate them, making sure that if the thief is located in one of them, he will get caught. Albert promised the President that the thief will be caught in no more than 2015 hours and needs your help in order to achieve that.

Input format:
There is no input for this problem.

Output format:
The first line of output contains integer N – duration of police search in hours. Each of the following N lines contains exactly 4 integers Xi1, Yi1, Xi2, Yi2 separated by spaces, that represent 2 districts (Xi1, Yi1), (Xi2, Yi2) which got investigated during i-th hour. Output is given in chronological order (i-th line contains districts investigated during i-th hour) and should guarantee that the thief is caught in no more than 2015 hours, regardless of thief’s initial position and movement.

- N ≤ 2015
- 1 ≤ X ≤ 1000
- 1 ≤ Y ≤ 2

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

Note:
Let's consider the following output:

2

5 1 50 2

8 1 80 2

This output is not guaranteed to catch the thief and is not correct. It is given to you only to show the expected output format. There exists a combination of an initial position and a movement strategy such that the police will not catch the thief.

Consider the following initial position and thief’s movement:

In the first hour, the thief is located in district (1,1). Police officers will search districts (5,1) and (50,2) and will not find him.

At the start of the second hour, the thief moves to district (2,2). Police officers will search districts (8,1) and (80,2) and will not find him.

Since there is no further investigation by the police, the thief escaped!

Example input:
В этой задаче нет примеров ввода-вывода.
This problem doesn't have sample input and output.

Example output:
Смотрите замечание ниже.
See the note below.

Editorial:
Spectator Riots
Contest: Bubble Cup 8 - Finals [Online Mirror]
Difficulty rating: 2800
Tags: geometry

It’s riot time on football stadium Ramacana! Raging fans have entered the field and the police find themselves in a difficult situation. The field can be represented as a square in the coordinate system defined by two diagonal vertices in (0,0) and (105, 105). The sides of that square are also considered to be inside the field, everything else is outside.

In the beginning, there are N fans on the field. For each fan we are given his speed, an integer vi as well as his integer coordinates (xi, yi). A fan with those coordinates might move and after one second he might be at any point (xi + p, yi + q) where 0 ≤ |p| + |q| ≤ vi. p, q are both integers.

Points that go outside of the square that represents the field are excluded and all others have equal probability of being the location of that specific fan after one second.

Andrej, a young and promising police officer, has sent a flying drone to take a photo of the riot from above. The drone’s camera works like this:

1. It selects three points with integer coordinates such that there is a chance of a fan appearing there after one second. They must not be collinear or the camera won’t work. It is guaranteed that not all of the initial positions of fans will be on the same line.
2. Camera focuses those points and creates a circle that passes through those three points. A photo is taken after one second (one second after the initial state).
3. Everything that is on the circle or inside it at the moment of taking the photo (one second after focusing the points) will be on the photo.

Your goal is to select those three points so that the expected number of fans seen on the photo is maximized. If there are more such selections, select those three points that give the circle with largest radius among them. If there are still more suitable selections, any one of them will be accepted. If your answer follows conditions above and radius of circle you return is smaller then the optimal one by 0.01, your output will be considered as correct.

No test will have optimal radius bigger than 1010.

Input format:
The first line contains the number of fans on the field, N. The next N lines contain three integers: xi ,yi, vi. They are the x-coordinate, y-coordinate and speed of fan i at the beginning of the one second interval considered in the task.

- 3 ≤ N ≤ 105
- 0 ≤ xi, yi ≤ 105
- 0 ≤ vi ≤ 1000
- All numbers are integers

Output format:
You need to output the three points that camera needs to select. Print them in three lines, with every line containing the x-coordinate, then y-coordinate, separated by a single space. The order of points does not matter.

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

Example input:
3
1 1 1
1 1 1
1 2 1

Example output:
2 2
2 1
1 0

Editorial:
Bulbo
Contest: Bubble Cup 8 - Finals [Online Mirror]
Difficulty rating: 2100
Tags: dp, greedy

Bananistan is a beautiful banana republic. Beautiful women in beautiful dresses. Beautiful statues of beautiful warlords. Beautiful stars in beautiful nights.

In Bananistan people play this crazy game – Bulbo. There’s an array of bulbs and player at the position, which represents one of the bulbs. The distance between two neighboring bulbs is 1. Before each turn player can change his position with cost |posnew - posold|. After that, a contiguous set of bulbs lights-up and player pays the cost that’s equal to the distance to the closest shining bulb. Then, all bulbs go dark again. The goal is to minimize your summed cost. I tell you, Bananistanians are spending their nights playing with bulbs.

Banana day is approaching, and you are hired to play the most beautiful Bulbo game ever. A huge array of bulbs is installed, and you know your initial position and all the light-ups in advance. You need to play the ideal game and impress Bananistanians, and their families.

Input format:
The first line contains number of turns n and initial position x. Next n lines contain two numbers lstart and lend, which represent that all bulbs from interval [lstart, lend] are shining this turn.

- 1 ≤ n ≤ 5000
- 1 ≤ x ≤ 109
- 1 ≤ lstart ≤ lend ≤ 109

Output format:
Output should contain a single number which represents the best result (minimum cost) that could be obtained by playing this Bulbo game.

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

Note:
Before 1. turn move to position 5

Before 2. turn move to position 9

Before 5. turn move to position 8

Example input:
5 4
2 7
9 16
8 10
9 17
1 6

Example output:
8

Editorial:
Run for beer
Contest: Bubble Cup 8 - Finals [Online Mirror]
Difficulty rating: 2200
Tags: dfs and similar, shortest paths

People in BubbleLand like to drink beer. Little do you know, beer here is so good and strong that every time you drink it your speed goes 10 times slower than before you drank it.

Birko lives in city Beergrade, but wants to go to city Beerburg. You are given a road map of BubbleLand and you need to find the fastest way for him. When he starts his journey in Beergrade his speed is 1. When he comes to a new city he always tries a glass of local beer, which divides his speed by 10.

The question here is what the minimal time for him to reach Beerburg is. If there are several paths with the same minimal time, pick the one that has least roads on it. If there is still more than one path, pick any.

It is guaranteed that there will be at least one path from Beergrade to Beerburg.

Input format:
The first line of input contains integer N — the number of cities in Bubbleland and integer M — the number of roads in this country. Cities are enumerated from 0 to N - 1, with city 0 being Beergrade, and city N - 1 being Beerburg. Each of the following M lines contains three integers a, b (a ≠ b) and len. These numbers indicate that there is a bidirectional road between cities a and b with length len.

- 2 ≤ N ≤ 105
- 1 ≤ M ≤ 105
- 0 ≤ len ≤ 9
- There is at most one road between two cities

Output format:
The first line of output should contain minimal time needed to go from Beergrade to Beerburg.

The second line of the output should contain the number of cities on the path from Beergrade to Beerburg that takes minimal time.

The third line of output should contain the numbers of cities on this path in the order they are visited, separated by spaces.

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

Example input:
8 10
0 1 1
1 2 5
2 7 6
0 3 2
3 7 3
0 4 0
4 5 0
5 7 2
0 6 0
6 7 7

Example output:
32
3
0 3 7

Editorial:
Bots
Contest: Bubble Cup 8 - Finals [Online Mirror]
Difficulty rating: 1800
Tags: combinatorics, dp, math, number theory

Sasha and Ira are two best friends. But they aren’t just friends, they are software engineers and experts in artificial intelligence. They are developing an algorithm for two bots playing a two-player game. The game is cooperative and turn based. In each turn, one of the players makes a move (it doesn’t matter which player, it's possible that players turns do not alternate).

Algorithm for bots that Sasha and Ira are developing works by keeping track of the state the game is in. Each time either bot makes a move, the state changes. And, since the game is very dynamic, it will never go back to the state it was already in at any point in the past.

Sasha and Ira are perfectionists and want their algorithm to have an optimal winning strategy. They have noticed that in the optimal winning strategy, both bots make exactly N moves each. But, in order to find the optimal strategy, their algorithm needs to analyze all possible states of the game (they haven’t learned about alpha-beta pruning yet) and pick the best sequence of moves.

They are worried about the efficiency of their algorithm and are wondering what is the total number of states of the game that need to be analyzed?

Input format:
The first and only line contains integer N.

- 1 ≤ N ≤ 106

Output format:
Output should contain a single integer – number of possible states modulo 109 + 7.

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

Note:
Start: Game is in state A.

- Turn 1: Either bot can make a move (first bot is red and second bot is blue), so there are two possible states after the first turn – B and C.
- Turn 2: In both states B and C, either bot can again make a turn, so the list of possible states is expanded to include D, E, F and G.
- Turn 3: Red bot already did N=2 moves when in state D, so it cannot make any more moves there. It can make moves when in state E, F and G, so states I, K and M are added to the list. Similarly, blue bot cannot make a move when in state G, but can when in D, E and F, so states H, J and L are added.
- Turn 4: Red bot already did N=2 moves when in states H, I and K, so it can only make moves when in J, L and M, so states P, R and S are added. Blue bot cannot make a move when in states J, L and M, but only when in H, I and K, so states N, O and Q are added.

Overall, there are 19 possible states of the game their algorithm needs to analyze.

Example input:
2

Example output:
19

Editorial:
Robots protection
Contest: Bubble Cup 8 - Finals [Online Mirror]
Difficulty rating: 2800
Tags: data structures

Company "Robots industries" produces robots for territory protection. Robots protect triangle territories — right isosceles triangles with catheti parallel to North-South and East-West directions.

Owner of some land buys and sets robots on his territory to protect it. From time to time, businessmen want to build offices on that land and want to know how many robots will guard it. You are to handle these queries.

Input format:
The first line contains integer N — width and height of the land, and integer Q — number of queries to handle.

Next Q lines contain queries you need to process.

Two types of queries:

1. 1 dir x y len — add a robot to protect a triangle. Depending on the value of dir, the values of x, y and len represent a different triangle:   dir = 1: Triangle is defined by the points (x, y), (x + len, y), (x, y + len)  dir = 2: Triangle is defined by the points (x, y), (x + len, y), (x, y - len)  dir = 3: Triangle is defined by the points (x, y), (x - len, y), (x, y + len)  dir = 4: Triangle is defined by the points (x, y), (x - len, y), (x, y - len)
2. 2 x y — output how many robots guard this point (robot guards a point if the point is inside or on the border of its triangle)

- 1 ≤ N ≤ 5000
- 1 ≤ Q ≤ 105
- 1 ≤ dir ≤ 4
- All points of triangles are within range [1, N]
- All numbers are positive integers

Output format:
For each second type query output how many robots guard this point. Each answer should be in a separate line.

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

Example input:
17 10
1 1 3 2 4
1 3 10 3 7
1 2 6 8 2
1 3 9 4 2
2 4 4
1 4 15 10 6
2 7 7
2 9 4
2 12 2
2 13 8

Example output:
2
2
2
0
1

Editorial:
Two Rival Students
Contest: Educational Codeforces Round 76 (Rated for Div. 2)
Difficulty rating: 800
Tags: greedy, math

You are the gym teacher in the school.

There are $$$n$$$ students in the row. And there are two rivalling students among them. The first one is in position $$$a$$$, the second in position $$$b$$$. Positions are numbered from $$$1$$$ to $$$n$$$ from left to right.

Since they are rivals, you want to maximize the distance between them. If students are in positions $$$p$$$ and $$$s$$$ respectively, then distance between them is $$$|p - s|$$$.

You can do the following operation at most $$$x$$$ times: choose two adjacent (neighbouring) students and swap them.

Calculate the maximum distance between two rivalling students after at most $$$x$$$ swaps.

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

The only line of each test case contains four integers $$$n$$$, $$$x$$$, $$$a$$$ and $$$b$$$ ($$$2 \le n \le 100$$$, $$$0 \le x \le 100$$$, $$$1 \le a, b \le n$$$, $$$a \neq b$$$) — the number of students in the row, the number of swaps which you can do, and positions of first and second rivaling students respectively.

Output format:
For each test case print one integer — the maximum distance between two rivaling students which you can obtain.

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

Note:
In the first test case you can swap students in positions $$$3$$$ and $$$4$$$. And then the distance between the rivals is equal to $$$|4 - 2| = 2$$$.

In the second test case you don't have to swap students.

In the third test case you can't swap students.

Example input:
3
5 1 3 2
100 33 100 1
6 0 2 3

Example output:
2
99
1

Editorial:
To solve the problem you need to understand two facts:
1. The answer can't be greater than $$$n - 1$$$;
2. If current distance between rivaling student if less then $$$n-1$$$ we always can increment this distance by one swap;
In means that answer is equal to $$$\min (n - 1, |a - b| + x)$$$.
Magic Stick
Contest: Educational Codeforces Round 76 (Rated for Div. 2)
Difficulty rating: 1000
Tags: math

Recently Petya walked in the forest and found a magic stick.

Since Petya really likes numbers, the first thing he learned was spells for changing numbers. So far, he knows only two spells that can be applied to a positive integer:

1. If the chosen number $$$a$$$ is even, then the spell will turn it into $$$\frac{3a}{2}$$$;
2. If the chosen number $$$a$$$ is greater than one, then the spell will turn it into $$$a-1$$$.

Note that if the number is even and greater than one, then Petya can choose which spell to apply.

Petya now has only one number $$$x$$$. He wants to know if his favorite number $$$y$$$ can be obtained from $$$x$$$ using the spells he knows. The spells can be used any number of times in any order. It is not required to use spells, Petya can leave $$$x$$$ as it is.

Input format:
The first line contains single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases. Each test case consists of two lines.

The first line of each test case contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le 10^9$$$) — the current number and the number that Petya wants to get.

Output format:
For the $$$i$$$-th test case print the answer on it — YES if Petya can get the number $$$y$$$ from the number $$$x$$$ using known spells, and NO otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).

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

Example input:
7
2 3
1 1
3 6
6 8
1 2
4 1
31235 6578234

Example output:
YES
YES
NO
YES
NO
YES
YES

Editorial:
$$$1$$$ cannot be transformed into any other number. $$$2$$$ can be transformed into $$$3$$$ or $$$1$$$, and $$$3$$$ can be transformed only into $$$2$$$. It means that if $$$x = 1$$$, then only $$$y = 1$$$ is reachable; and if $$$x = 2$$$ or $$$x = 3$$$, then $$$y$$$ should be less than $$$4$$$.
Otherwise, we can make $$$x$$$ as large as we want, so if $$$x > 3$$$, any $$$y$$$ is reachable.
Bear and Raspberry
Contest: Codeforces Round 226 (Div. 2)
Difficulty rating: 1000
Tags: brute force, greedy, implementation

The bear decided to store some raspberry for the winter. He cunningly found out the price for a barrel of honey in kilos of raspberry for each of the following n days. According to the bear's data, on the i-th (1 ≤ i ≤ n) day, the price for one barrel of honey is going to is xi kilos of raspberry.

Unfortunately, the bear has neither a honey barrel, nor the raspberry. At the same time, the bear's got a friend who is ready to lend him a barrel of honey for exactly one day for c kilograms of raspberry. That's why the bear came up with a smart plan. He wants to choose some day d (1 ≤ d < n), lent a barrel of honey and immediately (on day d) sell it according to a daily exchange rate. The next day (d + 1) the bear wants to buy a new barrel of honey according to a daily exchange rate (as he's got some raspberry left from selling the previous barrel) and immediately (on day d + 1) give his friend the borrowed barrel of honey as well as c kilograms of raspberry for renting the barrel.

The bear wants to execute his plan at most once and then hibernate. What maximum number of kilograms of raspberry can he earn? Note that if at some point of the plan the bear runs out of the raspberry, then he won't execute such a plan.

Input format:
The first line contains two space-separated integers, n and c (2 ≤ n ≤ 100, 0 ≤ c ≤ 100), — the number of days and the number of kilos of raspberry that the bear should give for borrowing the barrel.

The second line contains n space-separated integers x1, x2, ..., xn (0 ≤ xi ≤ 100), the price of a honey barrel on day i.

Output format:
Print a single integer — the answer to the problem.

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

Note:
In the first sample the bear will lend a honey barrel at day 3 and then sell it for 7. Then the bear will buy a barrel for 3 and return it to the friend. So, the profit is (7 - 3 - 1) = 3.

In the second sample bear will lend a honey barrel at day 1 and then sell it for 100. Then the bear buy the barrel for 1 at the day 2. So, the profit is (100 - 1 - 2) = 97.

Example input:
5 1
5 10 7 3 20

Example output:
3

Example input:
6 2
100 1 10 40 10 40

Example output:
97

Editorial:
Bear and Strings
Contest: Codeforces Round 226 (Div. 2)
Difficulty rating: 1200
Tags: brute force, greedy, implementation, math, strings

The bear has a string s = s1s2... s|s| (record |s| is the string's length), consisting of lowercase English letters. The bear wants to count the number of such pairs of indices i, j (1 ≤ i ≤ j ≤ |s|), that string x(i, j) = sisi + 1... sj contains at least one string "bear" as a substring.

String x(i, j) contains string "bear", if there is such index k (i ≤ k ≤ j - 3), that sk = b, sk + 1 = e, sk + 2 = a, sk + 3 = r.

Help the bear cope with the given problem.

Input format:
The first line contains a non-empty string s (1 ≤ |s| ≤ 5000). It is guaranteed that the string only consists of lowercase English letters.

Output format:
Print a single number — the answer to the problem.

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

Note:
In the first sample, the following pairs (i, j) match: (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9).

In the second sample, the following pairs (i, j) match: (1,  4), (1,  5), (1,  6), (1,  7), (1,  8), (1,  9), (1,  10), (1,  11), (2,  10), (2,  11), (3,  10), (3,  11), (4,  10), (4,  11), (5,  10), (5,  11), (6,  10), (6,  11), (7,  10), (7,  11).

Example input:
bearbtear

Example output:
6

Example input:
bearaabearc

Example output:
20

Editorial:
Bear and Prime Numbers
Contest: Codeforces Round 226 (Div. 2)
Difficulty rating: 1700
Tags: binary search, brute force, data structures, dp, implementation, math, number theory

Recently, the bear started studying data structures and faced the following problem.

You are given a sequence of integers x1, x2, ..., xn of length n and m queries, each of them is characterized by two integers li, ri. Let's introduce f(p) to represent the number of such indexes k, that xk is divisible by p. The answer to the query li, ri is the sum: $$\sum_{p \in S(l_i, r_i)} f(p)$$, where S(li, ri) is a set of prime numbers from segment [li, ri] (both borders are included in the segment).

Help the bear cope with the problem.

Input format:
The first line contains integer n (1 ≤ n ≤ 106). The second line contains n integers x1, x2, ..., xn (2 ≤ xi ≤ 107). The numbers are not necessarily distinct.

The third line contains integer m (1 ≤ m ≤ 50000). Each of the following m lines contains a pair of space-separated integers, li and ri (2 ≤ li ≤ ri ≤ 2·109) — the numbers that characterize the current query.

Output format:
Print m integers — the answers to the queries on the order the queries appear in the input.

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

Note:
Consider the first sample. Overall, the first sample has 3 queries.

1. The first query l = 2, r = 11 comes. You need to count f(2) + f(3) + f(5) + f(7) + f(11) = 2 + 1 + 4 + 2 + 0 = 9.
2. The second query comes l = 3, r = 12. You need to count f(3) + f(5) + f(7) + f(11) = 1 + 4 + 2 + 0 = 7.
3. The third query comes l = 4, r = 4. As this interval has no prime numbers, then the sum equals 0.

Example input:
6
5 5 7 10 14 15
3
2 11
3 12
4 4

Example output:
9
7
0

Example input:
7
2 3 5 7 11 4 8
2
8 10
2 123

Example output:
0
7

Editorial: