1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Valera and Plates
Contest: Codeforces Round 216 (Div. 2)
Difficulty rating: 900
Tags: greedy, implementation

Valera is a lazy student. He has m clean bowls and k clean plates.

Valera has made an eating plan for the next n days. As Valera is lazy, he will eat exactly one dish per day. At that, in order to eat a dish, he needs exactly one clean plate or bowl. We know that Valera can cook only two types of dishes. He can eat dishes of the first type from bowls and dishes of the second type from either bowls or plates.

When Valera finishes eating, he leaves a dirty plate/bowl behind. His life philosophy doesn't let him eat from dirty kitchenware. So sometimes he needs to wash his plate/bowl before eating. Find the minimum number of times Valera will need to wash a plate/bowl, if he acts optimally.

Input format:
The first line of the input contains three integers n, m, k (1 ≤ n, m, k ≤ 1000) — the number of the planned days, the number of clean bowls and the number of clean plates.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 2). If ai equals one, then on day i Valera will eat a first type dish. If ai equals two, then on day i Valera will eat a second type dish.

Output format:
Print a single integer — the minimum number of times Valera will need to wash a plate/bowl.

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

Note:
In the first sample Valera will wash a bowl only on the third day, so the answer is one.

In the second sample, Valera will have the first type of the dish during all four days, and since there are only three bowls, he will wash a bowl exactly once.

In the third sample, Valera will have the second type of dish for all three days, and as they can be eaten from either a plate or a bowl, he will never need to wash a plate/bowl.

Example input:
3 1 1
1 2 1

Example output:
1

Example input:
4 3 1
1 1 1 1

Example output:
1

Editorial:
Valera and Contest
Contest: Codeforces Round 216 (Div. 2)
Difficulty rating: 1400
Tags: constructive algorithms, implementation, math

Valera loves to participate in competitions. Especially in programming contests. Today he has participated in the contest with his team, consisting of n students (including Valera). This contest was an individual competition, so each student in the team solved problems individually.

After the contest was over, Valera was interested in results. He found out that:

- each student in the team scored at least l points and at most r points;
- in total, all members of the team scored exactly sall points;
- the total score of the k members of the team who scored the most points is equal to exactly sk; more formally, if a1, a2, ..., an is the sequence of points earned by the team of students in the non-increasing order (a1 ≥ a2 ≥ ... ≥ an), then sk = a1 + a2 + ... + ak.

However, Valera did not find out exactly how many points each of n students scored. Valera asked you to recover any distribution of scores between the students of the team, such that all the conditions above are met.

Input format:
The first line of the input contains exactly six integers n, k, l, r, sall, sk (1 ≤ n, k, l, r ≤ 1000; l ≤ r; k ≤ n; 1 ≤ sk ≤ sall ≤ 106).

It's guaranteed that the input is such that the answer exists.

Output format:
Print exactly n integers a1, a2, ..., an — the number of points each student scored. If there are multiple solutions, you can print any of them. You can print the distribution of points in any order.

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

Example input:
5 3 1 3 13 9

Example output:
2 3 2 3 3

Example input:
5 3 1 3 15 9

Example output:
3 3 3 3 3

Editorial:
Valera and Elections
Contest: Codeforces Round 216 (Div. 2)
Difficulty rating: 1600
Tags: dfs and similar, graphs, trees

The city Valera lives in is going to hold elections to the city Parliament.

The city has n districts and n - 1 bidirectional roads. We know that from any district there is a path along the roads to any other district. Let's enumerate all districts in some way by integers from 1 to n, inclusive. Furthermore, for each road the residents decided if it is the problem road or not. A problem road is a road that needs to be repaired.

There are n candidates running the elections. Let's enumerate all candidates in some way by integers from 1 to n, inclusive. If the candidate number i will be elected in the city Parliament, he will perform exactly one promise — to repair all problem roads on the way from the i-th district to the district 1, where the city Parliament is located.

Help Valera and determine the subset of candidates such that if all candidates from the subset will be elected to the city Parliament, all problem roads in the city will be repaired. If there are several such subsets, you should choose the subset consisting of the minimum number of candidates.

Input format:
The first line contains a single integer n (2 ≤ n ≤ 105) — the number of districts in the city.

Then n - 1 lines follow. Each line contains the description of a city road as three positive integers xi, yi, ti (1 ≤ xi, yi ≤ n, 1 ≤ ti ≤ 2) — the districts connected by the i-th bidirectional road and the road type. If ti equals to one, then the i-th road isn't the problem road; if ti equals to two, then the i-th road is the problem road.

It's guaranteed that the graph structure of the city is a tree.

Output format:
In the first line print a single non-negative number k — the minimum size of the required subset of candidates. Then on the second line print k space-separated integers a1, a2, ... ak — the numbers of the candidates that form the required subset. If there are multiple solutions, you are allowed to print any of them.

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

Example input:
5
1 2 2
2 3 2
3 4 2
4 5 2

Example output:
1
5

Example input:
5
1 2 1
2 3 2
2 4 1
4 5 1

Example output:
1
3

Editorial:
Valera and Fools
Contest: Codeforces Round 216 (Div. 2)
Difficulty rating: 2200
Tags: dfs and similar, dp, graphs, shortest paths

One fine morning, n fools lined up in a row. After that, they numbered each other with numbers from 1 to n, inclusive. Each fool got a unique number. The fools decided not to change their numbers before the end of the fun.

Every fool has exactly k bullets and a pistol. In addition, the fool number i has probability of pi (in percent) that he kills the fool he shoots at.

The fools decided to have several rounds of the fun. Each round of the fun looks like this: each currently living fool shoots at another living fool with the smallest number (a fool is not stupid enough to shoot at himself). All shots of the round are perfomed at one time (simultaneously). If there is exactly one living fool, he does not shoot.

Let's define a situation as the set of numbers of all the living fools at the some time. We say that a situation is possible if for some integer number j (0 ≤ j ≤ k) there is a nonzero probability that after j rounds of the fun this situation will occur.

Valera knows numbers p1, p2, ..., pn and k. Help Valera determine the number of distinct possible situations.

Input format:
The first line contains two integers n, k (1 ≤ n, k ≤ 3000) — the initial number of fools and the number of bullets for each fool.

The second line contains n integers p1, p2, ..., pn (0 ≤ pi ≤ 100) — the given probabilities (in percent).

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, any situation is possible, except for situation {1, 2}.

In the second sample there is exactly one fool, so he does not make shots.

In the third sample the possible situations are {1, 2} (after zero rounds) and the "empty" situation {} (after one round).

In the fourth sample, the only possible situation is {1, 2, 3}.

Example input:
3 3
50 50 50

Example output:
7

Example input:
1 1
100

Example output:
1

Editorial:
Valera and Queries
Contest: Codeforces Round 216 (Div. 2)
Difficulty rating: 2200
Tags: binary search, data structures

Valera loves segments. He has recently come up with one interesting problem.

The Ox axis of coordinates has n segments, the i-th segment starts in position li and ends in position ri (we will mark it as [li, ri]). Your task is to process m queries, each consists of number cnti and a set of cnti coordinates of points located on the Ox axis. The answer to the query is the number of segments, such that each of them contains at least one point from the query. Segment [l, r] contains point q, if l ≤ q ≤ r.

Valera found the solution of this problem too difficult. So he asked you to help him. Help Valera.

Input format:
The first line contains two integers n, m (1 ≤ n, m ≤ 3·105) — the number of segments on the axis of coordinates and the number of queries.

Next n lines contain the descriptions of the segments. The i-th line contains two positive integers li, ri (1 ≤ li ≤ ri ≤ 106) — the borders of the i-th segment.

Next m lines contain the description of the queries, one per line. Each line starts from integer cnti (1 ≤ cnti ≤ 3·105) — the number of points in the i-th query. Then the line contains cnti distinct positive integers p1, p2, ..., pcnti (1 ≤ p1 < p2 < ... < pcnti ≤ 106) — the coordinates of points in the i-th query.

It is guaranteed that the total number of points in all queries doesn't exceed 3·105.

Output format:
Print m non-negative integers, where the i-th number is the response to the i-th query.

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

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

Example output:
3
1
0

Editorial:
Grasshopper on a Line
Contest: Educational Codeforces Round 149 (Rated for Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, math

You are given two integers $$$x$$$ and $$$k$$$. Grasshopper starts in a point $$$0$$$ on an OX axis. In one move, it can jump some integer distance, that is not divisible by $$$k$$$, to the left or to the right.

What's the smallest number of moves it takes the grasshopper to reach point $$$x$$$? What are these moves? If there are multiple answers, print any of them.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of testcases.

The only line of each testcase contains two integers $$$x$$$ and $$$k$$$ ($$$1 \le x \le 100$$$; $$$2 \le k \le 100$$$) — the endpoint and the constraint on the jumps, respectively.

Output format:
For each testcase, in the first line, print a single integer $$$n$$$ — the smallest number of moves it takes the grasshopper to reach point $$$x$$$.

In the second line, print $$$n$$$ integers, each of them not divisible by $$$k$$$. A positive integer would mean jumping to the right, a negative integer would mean jumping to the left. The endpoint after the jumps should be exactly $$$x$$$.

Each jump distance should be from $$$-10^9$$$ to $$$10^9$$$. In can be shown that, for any solution with the smallest number of jumps, there exists a solution with the same number of jumps such that each jump is from $$$-10^9$$$ to $$$10^9$$$.

It can be shown that the answer always exists under the given constraints. If there are multiple answers, print any of them.

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

Example input:
3
10 2
10 3
3 4

Example output:
2
7 3
1
10
1
3

Editorial:
When $$$x$$$ is not divisible by $$$k$$$, the grasshopper can reach $$$x$$$ in just one jump.
Otherwise, you can show that two jumps are always enough. For example, jumps $$$1$$$ and $$$x-1$$$. $$$1$$$ is not divisible by any $$$k > 1$$$. Also, $$$x$$$ and $$$x-1$$$ can't be divisible by any $$$k > 1$$$ at the same time.
Privatization
Contest: VK Cup 2012 Finals
Difficulty rating: 3000

There is a developed network of flights between Berland and Beerland. All of them belong to the Berland state company BerAvia. Each flight connects some Berland city with some Beerland city. For each flight airplanes fly in both directions.

Changes are coming to Berland — the state decided to privatize BerAvia, namely, to sell out all flights to t private companies. Each of these companies wants to get the maximal number of flights, so if the Berland flights are sold unevenly, Berland can be accused of partiality. Berland Government decided to sell the flights as evenly as possible between the t companies.

The unevenness of the distribution of flights between companies is calculated as follows. For each city i (both Berland and Beerland) we'll calculate the value of

$${ w } _ { i } = \operatorname* { m a x } _ { j } a _ { i j } - \operatorname* { m i n } _ { j } a _ { i j },$$

Help the Berland government come up with the most even distribution plan of selling flights.

Input format:
The first input line contains four integers n, m, k and t (1 ≤ n, m, t ≤ 200;1 ≤ k ≤ 5000), where n, m are the numbers of cities in Berland and Beerland, correspondingly, k is the number of flights between them, and t is the number of private companies. Next k lines describe the flights, one per line, as pairs of positive integers xi, yi (1 ≤ xi ≤ n;1 ≤ yi ≤ m), where xi and yi are the indexes of cities in Berland and Beerland, correspondingly, connected by the i-th flight. There is at most one flight between any pair of cities, each flight connects cities of different countries. The cities in Berland are indexed from 1 to n, and in Beerland — from 1 to m.

Output format:
Print the unevenness of the sought plan on the first line. On the second line print a sequence of k integers c1, c2, ..., ck (1 ≤ ci ≤ t), where ci is the index of the company that should buy the i-th flight. Assume that the flights are indexed from 1 to k in the order they appear in the input. If there are multiple solutions, print any of them.

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

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

Example output:
4
2 1 2 1 2 1 2 2

Editorial:
Polycarpus is Looking for Good Substrings
Contest: VK Cup 2012 Finals
Difficulty rating: 2300

We'll call string s[a, b] = sasa + 1... sb (1 ≤ a ≤ b ≤ |s|) a substring of string s = s1s2... s|s|, where |s| is the length of string s.

The trace of a non-empty string t is a set of characters that the string consists of. For example, the trace of string "aab" equals {'a', 'b'}.

Let's consider an arbitrary string s and the set of its substrings with trace equal to C. We will denote the number of substrings from this set that are maximal by inclusion by r(C, s). Substring s[a, b] of length n = b - a + 1 belonging to some set is called maximal by inclusion, if there is no substring s[x, y] in this set with length greater than n, such that 1 ≤ x ≤ a ≤ b ≤ y ≤ |s|. Two substrings of string s are considered different even if they are equal but they are located at different positions of s.

Polycarpus got a challenging practical task on a stringology exam. He must do the following: given string s and non-empty sets of characters C1, C2, ..., Cm, find r(Ci, s) for each set Ci. Help Polycarpus to solve the problem as he really doesn't want to be expelled from the university and go to the army!

Input format:
The first line contains a non-empty string s (1 ≤ |s| ≤ 106).

The second line contains a single integer m (1 ≤ m ≤ 104). Next m lines contain descriptions of sets Ci. The i-th line contains string ci such that its trace equals Ci. It is guaranteed that all characters of each string ci are different.

Note that Ci are not necessarily different. All given strings consist of lowercase English letters.

Output format:
Print m integers — the i-th integer must equal r(Ci, s).

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

Example input:
aaaaa
2
a
a

Example output:
1
1

Example input:
abacaba
3
ac
ba
a

Example output:
1
2
4

Editorial:
Cowboys
Contest: VK Cup 2012 Finals
Difficulty rating: 2100
Tags: combinatorics

A very tense moment: n cowboys stand in a circle and each one points his colt at a neighbor. Each cowboy can point the colt to the person who follows or precedes him in clockwise direction. Human life is worthless, just like in any real western.

The picture changes each second! Every second the cowboys analyse the situation and, if a pair of cowboys realize that they aim at each other, they turn around. In a second all such pairs of neighboring cowboys aiming at each other turn around. All actions happen instantaneously and simultaneously in a second.

We'll use character "A" to denote a cowboy who aims at his neighbour in the clockwise direction, and character "B" for a cowboy who aims at his neighbour in the counter clockwise direction. Then a string of letters "A" and "B" will denote the circle of cowboys, the record is made from the first of them in a clockwise direction.

For example, a circle that looks like "ABBBABBBA" after a second transforms into "BABBBABBA" and a circle that looks like "BABBA" transforms into "ABABB".

This picture illustrates how the circle "BABBA" transforms into "ABABB"

A second passed and now the cowboys' position is described by string s. Your task is to determine the number of possible states that lead to s in a second. Two states are considered distinct if there is a cowboy who aims at his clockwise neighbor in one state and at his counter clockwise neighbor in the other state.

Input format:
The input data consists of a single string s. Its length is from 3 to 100 characters, inclusive. Line s consists of letters "A" and "B".

Output format:
Print the sought number of states.

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

Note:
In the first sample the possible initial states are "ABBBABBAB" and "ABBBABBBA".

In the second sample the possible initial states are "AABBB" and "BABBA".

Example input:
BABBBABBA

Example output:
2

Example input:
ABABB

Example output:
2

Editorial:
Cutting a Fence
Contest: VK Cup 2012 Finals
Difficulty rating: 2500

Vasya the carpenter has an estate that is separated from the wood by a fence. The fence consists of n planks put in a line. The fence is not closed in a circle. The planks are numbered from left to right from 1 to n, the i-th plank is of height ai. All planks have the same width, the lower edge of each plank is located at the ground level.

Recently a local newspaper "Malevich and Life" wrote that the most fashionable way to decorate a fence in the summer is to draw a fuchsia-colored rectangle on it, the lower side of the rectangle must be located at the lower edge of the fence.

Vasya is delighted with this idea! He immediately bought some fuchsia-colored paint and began to decide what kind of the rectangle he should paint. Vasya is sure that the rectangle should cover k consecutive planks. In other words, he will paint planks number x, x + 1, ..., x + k - 1 for some x (1 ≤ x ≤ n - k + 1). He wants to paint the rectangle of maximal area, so the rectangle height equals min ai for x ≤ i ≤ x + k - 1, x is the number of the first colored plank.

Vasya has already made up his mind that the rectangle width can be equal to one of numbers of the sequence k1, k2, ..., km. For each ki he wants to know the expected height of the painted rectangle, provided that he selects x for such fence uniformly among all n - ki + 1 possible values. Help him to find the expected heights.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 106) — the number of planks in the fence. The second line contains a sequence of integers a1, a2, ..., an (1 ≤ ai ≤ 109) where ai is the height of the i-th plank of the fence.

The third line contains an integer m (1 ≤ m ≤ 106) and the next line contains m space-separated integers k1, k2, ..., km (1 ≤ ki ≤ n) where ki is the width of the desired fuchsia-colored rectangle in planks.

Output format:
Print m whitespace-separated real numbers, the i-th number equals the expected value of the rectangle height, if its width in planks equals ki. The value will be considered correct if its absolute or relative error doesn't exceed 10 - 9.

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

Note:
Let's consider the first sample test.

- There are three possible positions of the fence for k1 = 1. For the first position (x = 1) the height is 3, for the second one (x = 2) the height is 2, for the third one (x = 3) the height is 1. As the fence position is chosen uniformly, the expected height of the fence equals $$\frac{3+2+1}{3}=2$$;
- There are two possible positions of the fence for k2 = 2. For the first position (x = 1) the height is 2, for the second one (x = 2) the height is 1. The expected height of the fence equals $${ \frac { 2 + 1 } { 2 } } = 1. 5$$;
- There is the only possible position of the fence for k3 = 3. The expected height of the fence equals 1.

Example input:
3
3 2 1
3
1 2 3

Example output:
2.000000000000000
1.500000000000000
1.000000000000000

Example input:
2
1 1
3
1 2 1

Example output:
1.000000000000000
1.000000000000000
1.000000000000000

Editorial:
IT Restaurants
Contest: VK Cup 2012 Finals
Difficulty rating: 1500

Сity N. has a huge problem with roads, food and IT-infrastructure. In total the city has n junctions, some pairs of them are connected by bidirectional roads. The road network consists of n - 1 roads, you can get from any junction to any other one by these roads. Yes, you're right — the road network forms an undirected tree.

Recently, the Mayor came up with a way that eliminates the problems with the food and the IT-infrastructure at the same time! He decided to put at the city junctions restaurants of two well-known cafe networks for IT professionals: "iMac D0naldz" and "Burger Bing". Since the network owners are not friends, it is strictly prohibited to place two restaurants of different networks on neighboring junctions. There are other requirements. Here's the full list:

- each junction must have at most one restaurant;
- each restaurant belongs either to "iMac D0naldz", or to "Burger Bing";
- each network should build at least one restaurant;
- there is no pair of junctions that are connected by a road and contains restaurants of different networks.

The Mayor is going to take a large tax from each restaurant, so he is interested in making the total number of the restaurants as large as possible.

Help the Mayor to analyze the situation. Find all such pairs of (a, b) that a restaurants can belong to "iMac D0naldz", b restaurants can belong to "Burger Bing", and the sum of a + b is as large as possible.

Input format:
The first input line contains integer n (3 ≤ n ≤ 5000) — the number of junctions in the city. Next n - 1 lines list all roads one per line. Each road is given as a pair of integers xi, yi (1 ≤ xi, yi ≤ n) — the indexes of connected junctions. Consider the junctions indexed from 1 to n.

It is guaranteed that the given road network is represented by an undirected tree with n vertexes.

Output format:
Print on the first line integer z — the number of sought pairs. Then print all sought pairs (a, b) in the order of increasing of the first component a.

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

Note:
The figure below shows the answers to the first test case. The junctions with "iMac D0naldz" restaurants are marked red and "Burger Bing" restaurants are marked blue.

Example input:
5
1 2
2 3
3 4
4 5

Example output:
3
1 3
2 2
3 1

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

Example output:
6
1 8
2 7
3 6
6 3
7 2
8 1

Editorial: