1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Supermarket
Contest: Codeforces Round 460 (Div. 2)
Difficulty rating: 800
Tags: brute force, greedy, implementation

We often go to supermarkets to buy some fruits or vegetables, and on the tag there prints the price for a kilo. But in some supermarkets, when asked how much the items are, the clerk will say that $$$a$$$ yuan for $$$b$$$ kilos (You don't need to care about what "yuan" is), the same as $$$a/b$$$ yuan for a kilo.

Now imagine you'd like to buy $$$m$$$ kilos of apples. You've asked $$$n$$$ supermarkets and got the prices. Find the minimum cost for those apples.

You can assume that there are enough apples in all supermarkets.

Input format:
The first line contains two positive integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 5\,000$$$, $$$1 \leq m \leq 100$$$), denoting that there are $$$n$$$ supermarkets and you want to buy $$$m$$$ kilos of apples.

The following $$$n$$$ lines describe the information of the supermarkets. Each line contains two positive integers $$$a, b$$$ ($$$1 \leq a, b \leq 100$$$), denoting that in this supermarket, you are supposed to pay $$$a$$$ yuan for $$$b$$$ kilos of apples.

Output format:
The only line, denoting the minimum cost for $$$m$$$ kilos of apples. Please make sure that the absolute or relative error between your answer and the correct answer won't exceed $$$10^{-6}$$$.

Formally, let your answer be $$$x$$$, and the jury's answer be $$$y$$$. Your answer is considered correct if $$$\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-6}$$$.

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

Note:
In the first sample, you are supposed to buy $$$5$$$ kilos of apples in supermarket $$$3$$$. The cost is $$$5/3$$$ yuan.

In the second sample, you are supposed to buy $$$1$$$ kilo of apples in supermarket $$$2$$$. The cost is $$$98/99$$$ yuan.

Example input:
3 5
1 2
3 4
1 3

Example output:
1.66666667

Example input:
2 1
99 100
98 99

Example output:
0.98989899

Editorial:
We can use greedy algorithm.
Obviously, if you can pay the least money for per kilo, you can pay the least money for $$$m$$$ kilos. So you can find the minimum of $$$a_i/b_i$$$, we say it is $$$x$$$. Then $$$m \cdot x$$$ is the final answer.
Time complexity: $$$\mathcal{O}(n)$$$.
Perfect Number
Contest: Codeforces Round 460 (Div. 2)
Difficulty rating: 1100
Tags: binary search, brute force, dp, implementation, number theory

We consider a positive integer perfect, if and only if the sum of its digits is exactly $$$10$$$. Given a positive integer $$$k$$$, your task is to find the $$$k$$$-th smallest perfect positive integer.

Input format:
A single line with a positive integer $$$k$$$ ($$$1 \leq k \leq 10\,000$$$).

Output format:
A single number, denoting the $$$k$$$-th smallest perfect integer.

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

Note:
The first perfect integer is $$$19$$$ and the second one is $$$28$$$.

Example input:
1

Example output:
19

Example input:
2

Example output:
28

Editorial:
Let's use brute force the find the answer.
You may find the answer is not too large (i.e. not bigger than $$$2 \cdot 10^7$$$), then you can find it in the given time limit.
You can check every possible answer from $$$1$$$ (or from $$$19$$$), until we find the $$$k$$$-th perfect integer.
That's all what we need to do. :P
Time complexity: $$$\mathcal{O}(answer)$$$. :P
Bonus1: Could you please come up with a faster brute force algorithm which doesn't need to check too many possible answers?
Bonus2: Can you solve the problem with a bigger $$$k$$$ (i.e. $$$k \leq 10^{18}$$$ or even bigger)?
Seat Arrangements
Contest: Codeforces Round 460 (Div. 2)
Difficulty rating: 1300
Tags: brute force, implementation

Suppose that you are in a campus and have to go for classes day by day. As you may see, when you hurry to a classroom, you surprisingly find that many seats there are already occupied. Today you and your friends went for class, and found out that some of the seats were occupied.

The classroom contains $$$n$$$ rows of seats and there are $$$m$$$ seats in each row. Then the classroom can be represented as an $$$n \times m$$$ matrix. The character '.' represents an empty seat, while '*' means that the seat is occupied. You need to find $$$k$$$ consecutive empty seats in the same row or column and arrange those seats for you and your friends. Your task is to find the number of ways to arrange the seats. Two ways are considered different if sets of places that students occupy differs.

Input format:
The first line contains three positive integers $$$n,m,k$$$ ($$$1 \leq n, m, k \leq 2\,000$$$), where $$$n,m$$$ represent the sizes of the classroom and $$$k$$$ is the number of consecutive seats you need to find.

Each of the next $$$n$$$ lines contains $$$m$$$ characters '.' or '*'. They form a matrix representing the classroom, '.' denotes an empty seat, and '*' denotes an occupied seat.

Output format:
A single number, denoting the number of ways to find $$$k$$$ empty seats in the same row or column.

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

Note:
In the first sample, there are three ways to arrange those seats. You can take the following seats for your arrangement.

- $$$(1,3)$$$, $$$(2,3)$$$
- $$$(2,2)$$$, $$$(2,3)$$$
- $$$(2,1)$$$, $$$(2,2)$$$

Example input:
2 3 2
**.
...

Example output:
3

Example input:
1 2 2
..

Example output:
1

Editorial:
We can find out how many consecutive empty positions in every row and column separately and add them together to form the final answer.
If the length of consecutive empty positions is no smaller than $$$k$$$, we assume that it is $$$len$$$. Then we can add $$$len-k+1$$$ to the final answer.
But, be careful. When $$$k=1$$$, the algorithm shown above is completely wrong. (Why?) So we need to deal with that situation separately. (I guess there will be lots of hacks :P)
Time complexity: $$$\mathcal{O}(nm)$$$.
Substring
Contest: Codeforces Round 460 (Div. 2)
Difficulty rating: 1700
Tags: dfs and similar, dp, graphs

You are given a graph with $$$n$$$ nodes and $$$m$$$ directed edges. One lowercase letter is assigned to each node. We define a path's value as the number of the most frequently occurring letter. For example, if letters on a path are "abaca", then the value of that path is $$$3$$$. Your task is find a path whose value is the largest.

Input format:
The first line contains two positive integers $$$n, m$$$ ($$$1 \leq n, m \leq 300\,000$$$), denoting that the graph has $$$n$$$ nodes and $$$m$$$ directed edges.

The second line contains a string $$$s$$$ with only lowercase English letters. The $$$i$$$-th character is the letter assigned to the $$$i$$$-th node.

Then $$$m$$$ lines follow. Each line contains two integers $$$x, y$$$ ($$$1 \leq x, y \leq n$$$), describing a directed edge from $$$x$$$ to $$$y$$$. Note that $$$x$$$ can be equal to $$$y$$$ and there can be multiple edges between $$$x$$$ and $$$y$$$. Also the graph can be not connected.

Output format:
Output a single line with a single integer denoting the largest value. If the value can be arbitrarily large, output -1 instead.

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

Note:
In the first sample, the path with largest value is $$$1 \to 3 \to 4 \to 5$$$. The value is $$$3$$$ because the letter 'a' appears $$$3$$$ times.

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

Example output:
3

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

Example output:
-1

Editorial:
It is obvious that we can use dynamic programming algorithm to solve this stupid problem. :P
We can make an array $$$f[i][j]$$$ to respect when you are at the point $$$i$$$, then how many letters $$$j$$$ you can get. Note that $$$i$$$ is ranging from $$$1$$$ to $$$n$$$ and $$$j$$$ is from $$$1$$$ to $$$26$$$.
Then, you can do this dynamic programming algorithm by topological sorting. Specifically, you can use $$$deg[i]$$$ to show how many edges that end at point $$$i$$$. First put all points $$$i$$$ which satisfy $$$deg[i]=0$$$ into a queue. When the queue is not empty, do the following steps repeatedly.
1. Take one point from the front of the queue. We say it is $$$i$$$.
2. Iterate all edges which begin at the point $$$i$$$. We say the endpoint of the edge is $$$k$$$. Then we update $$$f[k][\cdot]$$$ using $$$f[i][\cdot]$$$. Finally we make $$$deg[k]$$$ minus by $$$1$$$. If $$$deg[k] = 0$$$, then we add the point $$$k$$$ into the queue.
3. Make a variable $$$cnt$$$ plus by $$$1$$$.
When there is no cycle in the graph, the queue will be empty with $$$cnt = n$$$. Then the answer is the maximum number among $$$f[i][j]$$$. If there are cycles in the graph, then $$$cnt$$$ cannot be $$$n$$$. Thus the answer can be arbitrarily large. In that situation, we should output -1.
Time complexity: $$$\mathcal{O}(m \cdot alpha)$$$, where $$$alpha$$$ is the size of the alphabet (i.e. $$$alpha = 26$$$).
Memory complexity: $$$\mathcal{O}(n \cdot alpha)$$$.
Congruence Equation
Contest: Codeforces Round 460 (Div. 2)
Difficulty rating: 2100
Tags: chinese remainder theorem, math, number theory

Given an integer $$$x$$$. Your task is to find out how many positive integers $$$n$$$ ($$$1 \leq n \leq x$$$) satisfy $$$$$$n \cdot a^n \equiv b \quad (\textrm{mod}\;p),$$$$$$ where $$$a, b, p$$$ are all known constants.

Input format:
The only line contains four integers $$$a,b,p,x$$$ ($$$2 \leq p \leq 10^6+3$$$, $$$1 \leq a,b < p$$$, $$$1 \leq x \leq 10^{12}$$$). It is guaranteed that $$$p$$$ is a prime.

Output format:
Print a single integer: the number of possible answers $$$n$$$.

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

Note:
In the first sample, we can see that $$$n=2$$$ and $$$n=8$$$ are possible answers.

Example input:
2 3 5 8

Example output:
2

Example input:
4 6 7 13

Example output:
1

Editorial:
Trying all integers from $$$1$$$ to $$$x$$$ is too slow to solve this problem. So we need to find out some features of that given equation.
Because we have $$$a^{p-1} \equiv 1 \quad (\textrm{mod}\;p)$$$ when $$$p$$$ is a prime, it is obvious that $$$a^z \; \textrm{mod} \; p$$$ falls into a loop and the looping section is $$$p-1$$$. Also, $$$z \; \textrm{mod} \; p$$$ has a looping section $$$p$$$. We can try to list a chart to show what $$$n \cdot a^n$$$ is with some specific $$$i, j$$$. (In the chart shown below, $$$n$$$ is equal to $$$i \cdot (p-1) + j$$$)

Proof for the chart shown above: For a certain $$$i, j$$$, we can see that $$$$$$n \cdot a^n \bmod p = ((i \cdot (p-1) + j) \bmod p) \cdot a ^ {(i \cdot (p-1) + j) \bmod (p - 1)} = (j - i) \cdot a^j \bmod p$$$$$$ And it's not hard for us to prove that $$$n \cdot a^n \bmod p$$$ has a looping section $$$p(p-1)$$$. So we don't need to list $$$i \geq p$$$.
Therefore, we can enumerate $$$j$$$ from $$$1$$$ to $$$p - 1$$$ and calculate $$$b \cdot a^{-j}$$$. Let's say the result is $$$y$$$, then we have $$$j - i \equiv y \quad (\textrm{mod} \; p)$$$ (You can refer to the chart shown above to see if it is). So for a certain $$$j$$$, the possible $$$i$$$ can only be $$$(j - y), p + (j - y), \ldots, p \cdot t + (j - y)$$$. Then we can calculate how many possible answers $$$n$$$ in this situation (i.e. decide the minimum and maximum possible $$$t$$$ using the given lower bound $$$1$$$ and upper bound $$$x$$$). Finally we add them together and get the answer.
Time complexity: $$$\mathcal{O}(p \log p)$$$ or $$$\mathcal{O}(p)$$$ depending on how you calculate $$$y = b \cdot a^{-j}$$$.
By the way, you can also try Chinese Reminder Theorem to solve this problem.
Alyona and Numbers
Contest: Codeforces Round 358 (Div. 2)
Difficulty rating: 1100
Tags: constructive algorithms, math, number theory

After finishing eating her bun, Alyona came up with two integers n and m. She decided to write down two columns of integers — the first column containing integers from 1 to n and the second containing integers from 1 to m. Now the girl wants to count how many pairs of integers she can choose, one from the first column and the other from the second column, such that their sum is divisible by 5.

Formally, Alyona wants to count the number of pairs of integers (x, y) such that 1 ≤ x ≤ n, 1 ≤ y ≤ m and $$(x+y) \mod 5$$ equals 0.

As usual, Alyona has some troubles and asks you to help.

Input format:
The only line of the input contains two integers n and m (1 ≤ n, m ≤ 1 000 000).

Output format:
Print the only integer — the number of pairs of integers (x, y) such that 1 ≤ x ≤ n, 1 ≤ y ≤ m and (x + y) is divisible by 5.

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

Note:
Following pairs are suitable in the first sample case:

- for x = 1 fits y equal to 4 or 9;
- for x = 2 fits y equal to 3 or 8;
- for x = 3 fits y equal to 2, 7 or 12;
- for x = 4 fits y equal to 1, 6 or 11;
- for x = 5 fits y equal to 5 or 10;
- for x = 6 fits y equal to 4 or 9.

Only the pair (1, 4) is suitable in the third sample case.

Example input:
6 12

Example output:
14

Example input:
11 14

Example output:
31

Editorial:
Alyona and Mex
Contest: Codeforces Round 358 (Div. 2)
Difficulty rating: 1200
Tags: sortings

Someone gave Alyona an array containing n positive integers a1, a2, ..., an. In one operation, Alyona can choose any element of the array and decrease it, i.e. replace with any positive integer that is smaller than the current one. Alyona can repeat this operation as many times as she wants. In particular, she may not apply any operation to the array at all.

Formally, after applying some operations Alyona will get an array of n positive integers b1, b2, ..., bn such that 1 ≤ bi ≤ ai for every 1 ≤ i ≤ n. Your task is to determine the maximum possible value of mex of this array.

Mex of an array in this problem is the minimum positive integer that doesn't appear in this array. For example, mex of the array containing 1, 3 and 4 is equal to 2, while mex of the array containing 2, 3 and 2 is equal to 1.

Input format:
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of elements in the Alyona's array.

The second line of the input contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the elements of the array.

Output format:
Print one positive integer — the maximum possible value of mex of the array after Alyona applies some (possibly none) operations.

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

Note:
In the first sample case if one will decrease the second element value to 2 and the fifth element value to 4 then the mex value of resulting array 1 2 3 3 4 will be equal to 5.

To reach the answer to the second sample case one must not decrease any of the array elements.

Example input:
5
1 3 3 3 6

Example output:
5

Example input:
2
2 1

Example output:
3

Editorial:
Alyona and the Tree
Contest: Codeforces Round 358 (Div. 2)
Difficulty rating: 1600
Tags: dfs and similar, dp, graphs, trees

Alyona decided to go on a diet and went to the forest to get some apples. There she unexpectedly found a magic rooted tree with root in the vertex 1, every vertex and every edge of which has a number written on.

The girl noticed that some of the tree's vertices are sad, so she decided to play with them. Let's call vertex v sad if there is a vertex u in subtree of vertex v such that dist(v, u) > au, where au is the number written on vertex u, dist(v, u) is the sum of the numbers written on the edges on the path from v to u.

Leaves of a tree are vertices connected to a single vertex by a single edge, but the root of a tree is a leaf if and only if the tree consists of a single vertex — root.

Thus Alyona decided to remove some of tree leaves until there will be no any sad vertex left in the tree. What is the minimum number of leaves Alyona needs to remove?

Input format:
In the first line of the input integer n (1 ≤ n ≤ 105) is given — the number of vertices in the tree.

In the second line the sequence of n integers a1, a2, ..., an (1 ≤ ai ≤ 109) is given, where ai is the number written on vertex i.

The next n - 1 lines describe tree edges: ith of them consists of two integers pi and ci (1 ≤ pi ≤ n,  - 109 ≤ ci ≤ 109), meaning that there is an edge connecting vertices i + 1 and pi with number ci written on it.

Output format:
Print the only integer — the minimum number of leaves Alyona needs to remove such that there will be no any sad vertex left in the tree.

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

Note:
The following image represents possible process of removing leaves from the tree:

Example input:
9
88 22 83 14 95 91 98 53 11
3 24
7 -8
1 67
1 64
9 65
5 12
6 -80
3 8

Example output:
5

Editorial:
Alyona and Strings
Contest: Codeforces Round 358 (Div. 2)
Difficulty rating: 1900
Tags: dp, strings

After returned from forest, Alyona started reading a book. She noticed strings s and t, lengths of which are n and m respectively. As usual, reading bored Alyona and she decided to pay her attention to strings s and t, which she considered very similar.

Alyona has her favourite positive integer k and because she is too small, k does not exceed 10. The girl wants now to choose k disjoint non-empty substrings of string s such that these strings appear as disjoint substrings of string t and in the same order as they do in string s. She is also interested in that their length is maximum possible among all variants.

Formally, Alyona wants to find a sequence of k non-empty strings p1, p2, p3, ..., pk satisfying following conditions:

- s can be represented as concatenation a1p1a2p2... akpkak + 1, where a1, a2, ..., ak + 1 is a sequence of arbitrary strings (some of them may be possibly empty);
- t can be represented as concatenation b1p1b2p2... bkpkbk + 1, where b1, b2, ..., bk + 1 is a sequence of arbitrary strings (some of them may be possibly empty);
- sum of the lengths of strings in sequence is maximum possible.

Please help Alyona solve this complicated problem and find at least the sum of the lengths of the strings in a desired sequence.

A substring of a string is a subsequence of consecutive characters of the string.

Input format:
In the first line of the input three integers n, m, k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10) are given — the length of the string s, the length of the string t and Alyona's favourite number respectively.

The second line of the input contains string s, consisting of lowercase English letters.

The third line of the input contains string t, consisting of lowercase English letters.

Output format:
In the only line print the only non-negative integer — the sum of the lengths of the strings in a desired sequence.

It is guaranteed, that at least one desired sequence exists.

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

Note:
The following image describes the answer for the second sample case:

Example input:
3 2 2
abc
ab

Example output:
2

Example input:
9 12 4
bbaaababb
abbbabbaaaba

Example output:
7

Editorial:
Alyona and Triangles
Contest: Codeforces Round 358 (Div. 2)
Difficulty rating: 2600
Tags: geometry, two pointers

You are given n points with integer coordinates on the plane. Points are given in a way such that there is no triangle, formed by any three of these n points, which area exceeds S.

Alyona tried to construct a triangle with integer coordinates, which contains all n points and which area doesn't exceed 4S, but, by obvious reason, had no success in that. Please help Alyona construct such triangle. Please note that vertices of resulting triangle are not necessarily chosen from n given points.

Input format:
In the first line of the input two integers n and S (3 ≤ n ≤ 5000, 1 ≤ S ≤ 1018) are given — the number of points given and the upper bound value of any triangle's area, formed by any three of given n points.

The next n lines describes given points: ith of them consists of two integers xi and yi ( - 108 ≤ xi, yi ≤ 108) — coordinates of ith point.

It is guaranteed that there is at least one triple of points not lying on the same line.

Output format:
Print the coordinates of three points — vertices of a triangle which contains all n points and which area doesn't exceed 4S.

Coordinates of every triangle's vertex should be printed on a separate line, every coordinate pair should be separated by a single space. Coordinates should be an integers not exceeding 109 by absolute value.

It is guaranteed that there is at least one desired triangle. If there is more than one answer, print any of them.

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

Example input:
4 1
0 0
1 0
0 1
1 1

Example output:
-1 0
2 0
0 2

Editorial:
C+=
Contest: Codeforces Global Round 8
Difficulty rating: 800
Tags: brute force, greedy, implementation, math

Leo has developed a new programming language C+=. In C+=, integer variables can only be changed with a "+=" operation that adds the right-hand side value to the left-hand side variable. For example, performing "a += b" when a = $$$2$$$, b = $$$3$$$ changes the value of a to $$$5$$$ (the value of b does not change).

In a prototype program Leo has two integer variables a and b, initialized with some positive values. He can perform any number of operations "a += b" or "b += a". Leo wants to test handling large integers, so he wants to make the value of either a or b strictly greater than a given value $$$n$$$. What is the smallest number of operations he has to perform?

Input format:
The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 100$$$) — the number of test cases.

Each of the following $$$T$$$ lines describes a single test case, and contains three integers $$$a, b, n$$$ ($$$1 \leq a, b \leq n \leq 10^9$$$) — initial values of a and b, and the value one of the variables has to exceed, respectively.

Output format:
For each test case print a single integer — the smallest number of operations needed. Separate answers with line breaks.

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

Note:
In the first case we cannot make a variable exceed $$$3$$$ in one operation. One way of achieving this in two operations is to perform "b += a" twice.

Example input:
2
1 2 3
5 4 100

Example output:
2
7

Editorial:
After any operation either $$$a$$$ or $$$b$$$ becomes $$$a + b$$$. Out of the two options, clearly it is better to increase the smaller number. For example, with numbers $$$2, 3$$$ we can either get a pair $$$2, 5$$$ or $$$3, 5$$$; to obtain larger numbers, the last pair is better in every way.
With this we can just simulate the process and count the number of steps. The worst case is $$$a = b = 1$$$, $$$n = 10^9$$$, where each new addition produces the next element of the Fibonacci sequence. At this point we can just run the simulation and find out that $$$43$$$ steps are always enough. In general, Fibonacci sequence grows exponentially, thus $$$O(\log n)$$$ steps are needed.