1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Hot Days
Contest: Codeforces Round 132 (Div. 2)
Difficulty rating: 1900
Tags: greedy

The official capital and the cultural capital of Berland are connected by a single road running through n regions. Each region has a unique climate, so the i-th (1 ≤ i ≤ n) region has a stable temperature of ti degrees in summer.

This summer a group of m schoolchildren wants to get from the official capital to the cultural capital to visit museums and sights. The trip organizers transport the children between the cities in buses, but sometimes it is very hot. Specifically, if the bus is driving through the i-th region and has k schoolchildren, then the temperature inside the bus is ti + k degrees.

Of course, nobody likes it when the bus is hot. So, when the bus drives through the i-th region, if it has more than Ti degrees inside, each of the schoolchild in the bus demands compensation for the uncomfortable conditions. The compensation is as large as xi rubles and it is charged in each region where the temperature in the bus exceeds the limit.

To save money, the organizers of the trip may arbitrarily add or remove extra buses in the beginning of the trip, and between regions (of course, they need at least one bus to pass any region). The organizers can also arbitrarily sort the children into buses, however, each of buses in the i-th region will cost the organizers costi rubles. Please note that sorting children into buses takes no money.

Your task is to find the minimum number of rubles, which the organizers will have to spend to transport all schoolchildren.

Input format:
The first input line contains two integers n and m (1 ≤ n ≤ 105; 1 ≤ m ≤ 106) — the number of regions on the way and the number of schoolchildren in the group, correspondingly. Next n lines contain four integers each: the i-th line contains ti, Ti, xi and costi (1 ≤ ti, Ti, xi, costi ≤ 106). The numbers in the lines are separated by single spaces.

Output format:
Print the only integer — the minimum number of roubles the organizers will have to spend to transport all schoolchildren.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

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

Note:
In the first sample the organizers will use only one bus to travel through the first region. However, the temperature in the bus will equal 30 + 10 = 40 degrees and each of 10 schoolchildren will ask for compensation. Only one bus will transport the group through the second region too, but the temperature inside won't exceed the limit. Overall, the organizers will spend 100 + 10 + 10 = 120 rubles.

Example input:
2 10
30 35 1 100
20 35 10 10

Example output:
120

Example input:
3 100
10 30 1000 1
5 10 1000 3
10 40 1000 100000

Example output:
200065

Editorial:
Periodical Numbers
Contest: Codeforces Round 132 (Div. 2)
Difficulty rating: 2100
Tags: combinatorics, dp, number theory

A non-empty string s is called binary, if it consists only of characters "0" and "1". Let's number the characters of binary string s from 1 to the string's length and let's denote the i-th character in string s as si.

Binary string s with length n is periodical, if there is an integer 1 ≤ k < n such that:

- k is a divisor of number n
- for all 1 ≤ i ≤ n - k, the following condition fulfills: si = si + k

For example, binary strings "101010" and "11" are periodical and "10" and "10010" are not.

A positive integer x is periodical, if its binary representation (without leading zeroes) is a periodic string.

Your task is to calculate, how many periodic numbers are in the interval from l to r (both ends are included).

Input format:
The single input line contains two integers l and r (1 ≤ l ≤ r ≤ 1018). The numbers are separated by a space.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output format:
Print a single integer, showing how many periodic numbers are in the interval from l to r (both ends are included).

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

Note:
In the first sample periodic numbers are 3, 7 and 10.

In the second sample periodic numbers are 31 and 36.

Example input:
1 10

Example output:
3

Example input:
25 38

Example output:
2

Editorial:
Arithmetic Array
Contest: Codeforces Round 726 (Div. 2)
Difficulty rating: 800
Tags: greedy, math

An array $$$b$$$ of length $$$k$$$ is called good if its arithmetic mean is equal to $$$1$$$. More formally, if $$$$$$\frac{b_1 + \cdots + b_k}{k}=1.$$$$$$

Note that the value $$$\frac{b_1+\cdots+b_k}{k}$$$ is not rounded up or down. For example, the array $$$[1,1,1,2]$$$ has an arithmetic mean of $$$1.25$$$, which is not equal to $$$1$$$.

You are given an integer array $$$a$$$ of length $$$n$$$. In an operation, you can append a non-negative integer to the end of the array. What's the minimum number of operations required to make the array good?

We have a proof that it is always possible with finitely many operations.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 50$$$) — the length of the initial array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1,\ldots,a_n$$$ ($$$-10^4\leq a_i \leq 10^4$$$), the elements of the array.

Output format:
For each test case, output a single integer — the minimum number of non-negative integers you have to append to the array so that the arithmetic mean of the array will be exactly $$$1$$$.

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

Note:
In the first test case, we don't need to add any element because the arithmetic mean of the array is already $$$1$$$, so the answer is $$$0$$$.

In the second test case, the arithmetic mean is not $$$1$$$ initially so we need to add at least one more number. If we add $$$0$$$ then the arithmetic mean of the whole array becomes $$$1$$$, so the answer is $$$1$$$.

In the third test case, the minimum number of elements that need to be added is $$$16$$$ since only non-negative integers can be added.

In the fourth test case, we can add a single integer $$$4$$$. The arithmetic mean becomes $$$\frac{-2+4}{2}$$$ which is equal to $$$1$$$.

Example input:
4
3
1 1 1
2
1 2
4
8 4 6 2
1
-2

Example output:
0
1
16
1

Editorial:
To make the arithmetic mean be equal to exactly $$$1$$$ the sum needs to be equal to the number of elements in the array.
Let's consider $$$3$$$ cases for this problem:
1) The sum of the array equals $$$n$$$: Here the answer is $$$0$$$ since the arithmetic mean of the array is initially $$$1$$$.
2) The sum of the array is smaller than $$$n$$$: The answer is always $$$1$$$ since we can add a single integer $$$k$$$ such that $$$sum + k = n + 1$$$ is satisfied and more specifically $$$k = n - sum + 1$$$.
3) The sum of the array is greater than $$$n$$$: The only number that we can insert and decreases the arithmetic mean is $$$0$$$. The number of $$$0$$$'s to add can be found by a loop of adding $$$0$$$'s until the number of elements is equal to the sum or by the simple formula of $$$sum-n$$$.
Bad Boy
Contest: Codeforces Round 726 (Div. 2)
Difficulty rating: 900
Tags: constructive algorithms, greedy, math

Riley is a very bad boy, but at the same time, he is a yo-yo master. So, he decided to use his yo-yo skills to annoy his friend Anton.

Anton's room can be represented as a grid with $$$n$$$ rows and $$$m$$$ columns. Let $$$(i, j)$$$ denote the cell in row $$$i$$$ and column $$$j$$$. Anton is currently standing at position $$$(i, j)$$$ in his room. To annoy Anton, Riley decided to throw exactly two yo-yos in cells of the room (they can be in the same cell).

Because Anton doesn't like yo-yos thrown on the floor, he has to pick up both of them and return back to the initial position. The distance travelled by Anton is the shortest path that goes through the positions of both yo-yos and returns back to $$$(i, j)$$$ by travelling only to adjacent by side cells. That is, if he is in cell $$$(x, y)$$$ then he can travel to the cells $$$(x + 1, y)$$$, $$$(x - 1, y)$$$, $$$(x, y + 1)$$$ and $$$(x, y - 1)$$$ in one step (if a cell with those coordinates exists).

Riley is wondering where he should throw these two yo-yos so that the distance travelled by Anton is maximized. But because he is very busy, he asked you to tell him.

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

The only line of each test case contains four integers $$$n$$$, $$$m$$$, $$$i$$$, $$$j$$$ ($$$1 \leq n, m \leq 10^9$$$, $$$1\le i\le n$$$, $$$1\le j\le m$$$) — the dimensions of the room, and the cell at which Anton is currently standing.

Output format:
For each test case, print four integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ ($$$1 \leq x_1, x_2 \leq n$$$, $$$1\le y_1, y_2\le m$$$) — the coordinates of where the two yo-yos should be thrown. They will be thrown at coordinates $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$.

If there are multiple answers, you may print any.

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

Note:
Here is a visualization of the first test case.

Example input:
7
2 3 1 1
4 4 1 2
3 5 2 2
5 1 2 1
3 1 3 1
1 1 1 1
1000000000 1000000000 1000000000 50

Example output:
1 2 2 3
4 1 4 4
3 1 1 5
5 1 1 1
1 1 2 1
1 1 1 1
50 1 1 1000000000

Editorial:
We can notice that the optimal strategy is to put the yoyos in the corners of the board. One solution may be checking the best distance for all pairs of corners. But, if we think a bit more, we can notice that placing the yoyos in opposite corners the distance will always be maximum possible (the distance always being $$$2 \cdot (n - 1) + 2 \cdot (m - 1)$$$). So, one possible answer is to always place the first yoyo in the top-left cell and the second one in the bottom-right cell. This is always optimal because, for any initial position of Anton, the distance will still be the same ($$$2 \cdot (n - 1) + 2 \cdot (m - 1)$$$), this being the largest possible distance. The distance can not get larger than that, because if we move one of the yoyos it will get closer to the other yoyo and the distance will decrease by $$$1$$$ or won't decrease, but it's impossible for it to increase.
K-Periodic Array
Contest: Codeforces Round 218 (Div. 2)
Difficulty rating: 1000
Tags: greedy, implementation, math

This task will exclusively concentrate only on the arrays where all elements equal 1 and/or 2.

Array a is k-period if its length is divisible by k and there is such array b of length k, that a is represented by array b written exactly $$\pi_{k}$$ times consecutively. In other words, array a is k-periodic, if it has period of length k.

For example, any array is n-periodic, where n is the array length. Array [2, 1, 2, 1, 2, 1] is at the same time 2-periodic and 6-periodic and array [1, 2, 1, 1, 2, 1, 1, 2, 1] is at the same time 3-periodic and 9-periodic.

For the given array a, consisting only of numbers one and two, find the minimum number of elements to change to make the array k-periodic. If the array already is k-periodic, then the required value equals 0.

Input format:
The first line of the input contains a pair of integers n, k (1 ≤ k ≤ n ≤ 100), where n is the length of the array and the value n is divisible by k. The second line contains the sequence of elements of the given array a1, a2, ..., an (1 ≤ ai ≤ 2), ai is the i-th element of the array.

Output format:
Print the minimum number of array elements we need to change to make the array k-periodic. If the array already is k-periodic, then print 0.

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

Note:
In the first sample it is enough to change the fourth element from 2 to 1, then the array changes to [2, 1, 2, 1, 2, 1].

In the second sample, the given array already is 4-periodic.

In the third sample it is enough to replace each occurrence of number two by number one. In this case the array will look as [1, 1, 1, 1, 1, 1, 1, 1, 1] — this array is simultaneously 1-, 3- and 9-periodic.

Example input:
6 2
2 1 2 2 2 1

Example output:
1

Example input:
8 4
1 1 2 1 1 1 2 1

Example output:
0

Editorial:
Fox Dividing Cheese
Contest: Codeforces Round 218 (Div. 2)
Difficulty rating: 1300
Tags: math, number theory

Two little greedy bears have found two pieces of cheese in the forest of weight a and b grams, correspondingly. The bears are so greedy that they are ready to fight for the larger piece. That's where the fox comes in and starts the dialog: "Little bears, wait a little, I want to make your pieces equal" "Come off it fox, how are you going to do that?", the curious bears asked. "It's easy", said the fox. "If the mass of a certain piece is divisible by two, then I can eat exactly a half of the piece. If the mass of a certain piece is divisible by three, then I can eat exactly two-thirds, and if the mass is divisible by five, then I can eat four-fifths. I'll eat a little here and there and make the pieces equal".

The little bears realize that the fox's proposal contains a catch. But at the same time they realize that they can not make the two pieces equal themselves. So they agreed to her proposal, but on one condition: the fox should make the pieces equal as quickly as possible. Find the minimum number of operations the fox needs to make pieces equal.

Input format:
The first line contains two space-separated integers a and b (1 ≤ a, b ≤ 109).

Output format:
If the fox is lying to the little bears and it is impossible to make the pieces equal, print -1. Otherwise, print the required minimum number of operations. If the pieces of the cheese are initially equal, the required number is 0.

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

Example input:
15 20

Example output:
3

Example input:
14 8

Example output:
-1

Editorial:
Hamburgers
Contest: Codeforces Round 218 (Div. 2)
Difficulty rating: 1600
Tags: binary search, brute force

Polycarpus loves hamburgers very much. He especially adores the hamburgers he makes with his own hands. Polycarpus thinks that there are only three decent ingredients to make hamburgers from: a bread, sausage and cheese. He writes down the recipe of his favorite "Le Hamburger de Polycarpus" as a string of letters 'B' (bread), 'S' (sausage) и 'C' (cheese). The ingredients in the recipe go from bottom to top, for example, recipe "ВSCBS" represents the hamburger where the ingredients go from bottom to top as bread, sausage, cheese, bread and sausage again.

Polycarpus has nb pieces of bread, ns pieces of sausage and nc pieces of cheese in the kitchen. Besides, the shop nearby has all three ingredients, the prices are pb rubles for a piece of bread, ps for a piece of sausage and pc for a piece of cheese.

Polycarpus has r rubles and he is ready to shop on them. What maximum number of hamburgers can he cook? You can assume that Polycarpus cannot break or slice any of the pieces of bread, sausage or cheese. Besides, the shop has an unlimited number of pieces of each ingredient.

Input format:
The first line of the input contains a non-empty string that describes the recipe of "Le Hamburger de Polycarpus". The length of the string doesn't exceed 100, the string contains only letters 'B' (uppercase English B), 'S' (uppercase English S) and 'C' (uppercase English C).

The second line contains three integers nb, ns, nc (1 ≤ nb, ns, nc ≤ 100) — the number of the pieces of bread, sausage and cheese on Polycarpus' kitchen. The third line contains three integers pb, ps, pc (1 ≤ pb, ps, pc ≤ 100) — the price of one piece of bread, sausage and cheese in the shop. Finally, the fourth line contains integer r (1 ≤ r ≤ 1012) — the number of rubles Polycarpus has.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output format:
Print the maximum number of hamburgers Polycarpus can make. If he can't make any hamburger, print 0.

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

Example input:
BBBSSC
6 4 1
1 2 3
4

Example output:
2

Example input:
BBC
1 10 1
1 10 1
21

Example output:
7

Editorial:
Vessels
Contest: Codeforces Round 218 (Div. 2)
Difficulty rating: 1800
Tags: data structures, dsu, implementation, trees

There is a system of n vessels arranged one above the other as shown in the figure below. Assume that the vessels are numbered from 1 to n, in the order from the highest to the lowest, the volume of the i-th vessel is ai liters.

Initially, all the vessels are empty. In some vessels water is poured. All the water that overflows from the i-th vessel goes to the (i + 1)-th one. The liquid that overflows from the n-th vessel spills on the floor.

Your task is to simulate pouring water into the vessels. To do this, you will need to handle two types of queries:

1. Add xi liters of water to the pi-th vessel;
2. Print the number of liters of water in the ki-th vessel.

When you reply to the second request you can assume that all the water poured up to this point, has already overflown between the vessels.

Input format:
The first line contains integer n — the number of vessels (1 ≤ n ≤ 2·105). The second line contains n integers a1, a2, ..., an — the vessels' capacities (1 ≤ ai ≤ 109). The vessels' capacities do not necessarily increase from the top vessels to the bottom ones (see the second sample). The third line contains integer m — the number of queries (1 ≤ m ≤ 2·105). Each of the next m lines contains the description of one query. The query of the first type is represented as "1 pi xi", the query of the second type is represented as "2 ki" (1 ≤ pi ≤ n, 1 ≤ xi ≤ 109, 1 ≤ ki ≤ n).

Output format:
For each query, print on a single line the number of liters of water in the corresponding vessel.

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

Example input:
2
5 10
6
1 1 4
2 1
1 2 5
1 1 4
2 1
2 2

Example output:
4
5
8

Example input:
3
5 10 8
6
1 1 12
2 2
1 1 6
1 3 2
2 2
2 3

Example output:
7
10
5

Editorial:
Subway Innovation
Contest: Codeforces Round 218 (Div. 2)
Difficulty rating: 2000
Tags: greedy, math, two pointers

Berland is going through tough times — the dirt price has dropped and that is a blow to the country's economy. Everybody knows that Berland is the top world dirt exporter!

The President of Berland was forced to leave only k of the currently existing n subway stations.

The subway stations are located on a straight line one after another, the trains consecutively visit the stations as they move. You can assume that the stations are on the Ox axis, the i-th station is at point with coordinate xi. In such case the distance between stations i and j is calculated by a simple formula |xi - xj|.

Currently, the Ministry of Transport is choosing which stations to close and which ones to leave. Obviously, the residents of the capital won't be too enthusiastic about the innovation, so it was decided to show the best side to the people. The Ministry of Transport wants to choose such k stations that minimize the average commute time in the subway!

Assuming that the train speed is constant (it is a fixed value), the average commute time in the subway is calculated as the sum of pairwise distances between stations, divided by the number of pairs (that is $$\frac{n \cdot (n-1)}{2}$$) and divided by the speed of the train.

Help the Minister of Transport to solve this difficult problem. Write a program that, given the location of the stations selects such k stations that the average commute time in the subway is minimized.

Input format:
The first line of the input contains integer n (3 ≤ n ≤ 3·105) — the number of the stations before the innovation. The second line contains the coordinates of the stations x1, x2, ..., xn ( - 108 ≤ xi ≤ 108). The third line contains integer k (2 ≤ k ≤ n - 1) — the number of stations after the innovation.

The station coordinates are distinct and not necessarily sorted.

Output format:
Print a sequence of k distinct integers t1, t2, ..., tk (1 ≤ tj ≤ n) — the numbers of the stations that should be left after the innovation in arbitrary order. Assume that the stations are numbered 1 through n in the order they are given in the input. The number of stations you print must have the minimum possible average commute time among all possible ways to choose k stations. If there are multiple such ways, you are allowed to print any of them.

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

Note:
In the sample testcase the optimal answer is to destroy the first station (with x = 1). The average commute time will be equal to 1 in this way.

Example input:
3
1 100 101
2

Example output:
2 3

Editorial:
Gift
Contest: All-Ukrainian School Olympiad in Informatics
Difficulty rating: 2200
Tags: dsu, graphs, sortings, trees

The kingdom of Olympia consists of N cities and M bidirectional roads. Each road connects exactly two cities and two cities can be connected with more than one road. Also it possible that some roads connect city with itself making a loop.

All roads are constantly plundered with bandits. After a while bandits became bored of wasting time in road robberies, so they suggested the king of Olympia to pay off. According to the offer, bandits want to get a gift consisted of gold and silver coins. Offer also contains a list of restrictions: for each road it is known gi — the smallest amount of gold and si — the smallest amount of silver coins that should be in the gift to stop robberies on the road. That is, if the gift contains a gold and b silver coins, then bandits will stop robberies on all the roads that gi ≤ a and si ≤ b.

Unfortunately kingdom treasury doesn't contain neither gold nor silver coins, but there are Olympian tugriks in it. The cost of one gold coin in tugriks is G, and the cost of one silver coin in tugriks is S. King really wants to send bandits such gift that for any two cities there will exist a safe path between them. Your task is to find the minimal cost in Olympian tugriks of the required gift.

Input format:
The first line of the input contains two integers N and M (2 ≤ N ≤ 200, 1 ≤ M ≤ 50 000) — the number of cities and the number of roads, respectively. The second line contains two integers G and S (1 ≤ G, S ≤ 109) — the prices of gold and silver coins in tugriks. The following M lines contain information about the offer. Each of the records in list is given as four integers xi, yi, gi, si, where xi and yi are the numbers of cities that the road connects and gi, si are minimal gold and silver coins requirements for the i-th road (1 ≤ xi, yi ≤ N, 1 ≤ gi, si ≤ 109). Cities are numbered from 1 to N. It is possible that there are more than one road between a pair of cities. It is possible that a road connects the city with itself.

Output format:
The output should contain the minimal cost of the gift in Olympian tugriks. If there is no gift that satisfies the given requirements output $$- 1$$.

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

Example input:
3 3
2 1
1 2 10 15
1 2 4 20
1 3 5 1

Example output:
30

Editorial: