1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Anya and Cubes
Contest: Codeforces Round 297 (Div. 2)
Difficulty rating: 2100
Tags: binary search, bitmasks, brute force, dp, math, meet-in-the-middle

Anya loves to fold and stick. Today she decided to do just that.

Anya has n cubes lying in a line and numbered from 1 to n from left to right, with natural numbers written on them. She also has k stickers with exclamation marks. We know that the number of stickers does not exceed the number of cubes.

Anya can stick an exclamation mark on the cube and get the factorial of the number written on the cube. For example, if a cube reads 5, then after the sticking it reads 5!, which equals 120.

You need to help Anya count how many ways there are to choose some of the cubes and stick on some of the chosen cubes at most k exclamation marks so that the sum of the numbers written on the chosen cubes after the sticking becomes equal to S. Anya can stick at most one exclamation mark on each cube. Can you do it?

Two ways are considered the same if they have the same set of chosen cubes and the same set of cubes with exclamation marks.

Input format:
The first line of the input contains three space-separated integers n, k and S (1 ≤ n ≤ 25, 0 ≤ k ≤ n, 1 ≤ S ≤ 1016) — the number of cubes and the number of stickers that Anya has, and the sum that she needs to get.

The second line contains n positive integers ai (1 ≤ ai ≤ 109) — the numbers, written on the cubes. The cubes in the input are described in the order from left to right, starting from the first one.

Multiple cubes can contain the same numbers.

Output format:
Output the number of ways to choose some number of cubes and stick exclamation marks on some of them so that the sum of the numbers became equal to the given number S.

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

Note:
In the first sample the only way is to choose both cubes and stick an exclamation mark on each of them.

In the second sample the only way is to choose both cubes but don't stick an exclamation mark on any of them.

In the third sample it is possible to choose any of the cubes in three ways, and also we may choose to stick or not to stick the exclamation mark on it. So, the total number of ways is six.

Example input:
2 2 30
4 3

Example output:
1

Example input:
2 2 7
4 3

Example output:
1

Editorial:
There Are Two Types Of Burgers
Contest: Educational Codeforces Round 71 (Rated for Div. 2)
Difficulty rating: 800
Tags: brute force, greedy, implementation, math

There are two types of burgers in your restaurant — hamburgers and chicken burgers! To assemble a hamburger you need two buns and a beef patty. To assemble a chicken burger you need two buns and a chicken cutlet.

You have $$$b$$$ buns, $$$p$$$ beef patties and $$$f$$$ chicken cutlets in your restaurant. You can sell one hamburger for $$$h$$$ dollars and one chicken burger for $$$c$$$ dollars. Calculate the maximum profit you can achieve.

You have to answer $$$t$$$ independent queries.

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

The first line of each query contains three integers $$$b$$$, $$$p$$$ and $$$f$$$ ($$$1 \le b, ~p, ~f \le 100$$$) — the number of buns, beef patties and chicken cutlets in your restaurant.

The second line of each query contains two integers $$$h$$$ and $$$c$$$ ($$$1 \le h, ~c \le 100$$$) — the hamburger and chicken burger prices in your restaurant.

Output format:
For each query print one integer — the maximum profit you can achieve.

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

Note:
In first query you have to sell two hamburgers and three chicken burgers. Your income is $$$2 \cdot 5 + 3 \cdot 10 = 40$$$.

In second query you have to ell one hamburgers and two chicken burgers. Your income is $$$1 \cdot 10 + 2 \cdot 12 = 34$$$.

In third query you can not create any type of burgers because because you have only one bun. So your income is zero.

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

Example output:
40
34
0

Editorial:
In this task you just can iterate over the numbers of hamburgers and chicken burgers you want to assemble, check that you have enough ingredients and update the answer.
If you want to sell $$$x$$$ hamburgers and $$$y$$$ chicken burgers then you need $$$x$$$ beef patties, $$$y$$$ chicken cutlets and $$$2(x+y)$$$ buns.
Square Filling
Contest: Educational Codeforces Round 71 (Rated for Div. 2)
Difficulty rating: 1200
Tags: constructive algorithms, greedy, implementation

You are given two matrices $$$A$$$ and $$$B$$$. Each matrix contains exactly $$$n$$$ rows and $$$m$$$ columns. Each element of $$$A$$$ is either $$$0$$$ or $$$1$$$; each element of $$$B$$$ is initially $$$0$$$.

You may perform some operations with matrix $$$B$$$. During each operation, you choose any submatrix of $$$B$$$ having size $$$2 \times 2$$$, and replace every element in the chosen submatrix with $$$1$$$. In other words, you choose two integers $$$x$$$ and $$$y$$$ such that $$$1 \le x < n$$$ and $$$1 \le y < m$$$, and then set $$$B_{x, y}$$$, $$$B_{x, y + 1}$$$, $$$B_{x + 1, y}$$$ and $$$B_{x + 1, y + 1}$$$ to $$$1$$$.

Your goal is to make matrix $$$B$$$ equal to matrix $$$A$$$. Two matrices $$$A$$$ and $$$B$$$ are equal if and only if every element of matrix $$$A$$$ is equal to the corresponding element of matrix $$$B$$$.

Is it possible to make these matrices equal? If it is, you have to come up with a sequence of operations that makes $$$B$$$ equal to $$$A$$$. Note that you don't have to minimize the number of operations.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 50$$$).

Then $$$n$$$ lines follow, each containing $$$m$$$ integers. The $$$j$$$-th integer in the $$$i$$$-th line is $$$A_{i, j}$$$. Each integer is either $$$0$$$ or $$$1$$$.

Output format:
If it is impossible to make $$$B$$$ equal to $$$A$$$, print one integer $$$-1$$$.

Otherwise, print any sequence of operations that transforms $$$B$$$ into $$$A$$$ in the following format: the first line should contain one integer $$$k$$$ — the number of operations, and then $$$k$$$ lines should follow, each line containing two integers $$$x$$$ and $$$y$$$ for the corresponding operation (set $$$B_{x, y}$$$, $$$B_{x, y + 1}$$$, $$$B_{x + 1, y}$$$ and $$$B_{x + 1, y + 1}$$$ to $$$1$$$). The condition $$$0 \le k \le 2500$$$ should hold.

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

Note:
The sequence of operations in the first example:

$$$\begin{matrix} 0 & 0 & 0 & & 1 & 1 & 0 & & 1 & 1 & 1 & & 1 & 1 & 1 \\ 0 & 0 & 0 & \rightarrow & 1 & 1 & 0 & \rightarrow & 1 & 1 & 1 & \rightarrow & 1 & 1 & 1 \\ 0 & 0 & 0 & & 0 & 0 & 0 & & 0 & 0 & 0 & & 0 & 1 & 1 \end{matrix}$$$

Example input:
3 3
1 1 1
1 1 1
0 1 1

Example output:
3
1 1
1 2
2 2

Example input:
3 3
1 0 1
1 0 1
0 0 0

Example output:
-1

Editorial:
It is quite obvious that we can't choose any submatrix that contains at least one zero in $$$A$$$. The contrary is also true — if a submatrix of $$$A$$$ consists of only ones, then there's no reason not to choose it (suppose there is an answer that does not choose it — then choosing this submatrix won't affect it).
So we may perform an operation on every submatrix of $$$B$$$ such that the corresponding submatrix in $$$A$$$ is filled with $$$1$$$'s, and check if our answer is correct.
Remainder Problem
Contest: Educational Codeforces Round 71 (Rated for Div. 2)
Difficulty rating: 2100
Tags: brute force, data structures, implementation

You are given an array $$$a$$$ consisting of $$$500000$$$ integers (numbered from $$$1$$$ to $$$500000$$$). Initially all elements of $$$a$$$ are zero.

You have to process two types of queries to this array:

- $$$1$$$ $$$x$$$ $$$y$$$ — increase $$$a_x$$$ by $$$y$$$;
- $$$2$$$ $$$x$$$ $$$y$$$ — compute $$$\sum\limits_{i \in R(x, y)} a_i$$$, where $$$R(x, y)$$$ is the set of all integers from $$$1$$$ to $$$500000$$$ which have remainder $$$y$$$ modulo $$$x$$$.

Can you process all the queries?

Input format:
The first line contains one integer $$$q$$$ ($$$1 \le q \le 500000$$$) — the number of queries.

Then $$$q$$$ lines follow, each describing a query. The $$$i$$$-th line contains three integers $$$t_i$$$, $$$x_i$$$ and $$$y_i$$$ ($$$1 \le t_i \le 2$$$). If $$$t_i = 1$$$, then it is a query of the first type, $$$1 \le x_i \le 500000$$$, and $$$-1000 \le y_i \le 1000$$$. If $$$t_i = 2$$$, then it it a query of the second type, $$$1 \le x_i \le 500000$$$, and $$$0 \le y_i < x_i$$$.

It is guaranteed that there will be at least one query of type $$$2$$$.

Output format:
For each query of type $$$2$$$ print one integer — the answer to it.

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

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

Example output:
4
4
0

Editorial:
Let's notice that if we process the queries of type $$$2$$$ naively, then each such query consumes $$$O(\frac{N}{x})$$$ time (where $$$N$$$ is the size of the array). So queries with large $$$x$$$ can be processed naively.
For queries with small $$$x$$$ ($$$x \le K$$$), we may notice two things:
• there are only $$$O(K^2)$$$ possible queries;
• each number in the array affects only $$$K$$$ possible queries.
So, for small $$$x$$$, we may maintain the exact answer for each query and modify it each time we modify an element in the array.
If we process naively all queries with $$$x > \sqrt{N}$$$ and maintain the answers for all queries with $$$x \le \sqrt{N}$$$, we will obtain a solution having time complexity $$$O(q \sqrt{N})$$$. Note that, as in most problems related to sqrt-heuristics, it may be optimal to choose the constant that is not exactly $$$\sqrt{N}$$$, but something similar to it (but most solutions should pass without tuning the constant).
Odd Selection
Contest: Codeforces Round 646 (Div. 2)
Difficulty rating: 1200
Tags: brute force, implementation, math

Shubham has an array $$$a$$$ of size $$$n$$$, and wants to select exactly $$$x$$$ elements from it, such that their sum is odd. These elements do not have to be consecutive. The elements of the array are not guaranteed to be distinct.

Tell him whether he can do so.

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

The first line of each test case contains two integers $$$n$$$ and $$$x$$$ $$$(1 \le x \le n \le 1000)$$$ — the length of the array and the number of elements you need to choose.

The next line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 1000)$$$ — elements of the array.

Output format:
For each test case, print "Yes" or "No" depending on whether it is possible to choose $$$x$$$ elements such that their sum is odd.

You may print every letter in any case you want.

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

Note:
For $$$1$$$st case: We must select element $$$999$$$, and the sum is odd.

For $$$2$$$nd case: We must select element $$$1000$$$, so overall sum is not odd.

For $$$3$$$rd case: We can select element $$$51$$$.

For $$$4$$$th case: We must select both elements $$$50$$$ and $$$51$$$  — so overall sum is odd.

For $$$5$$$th case: We must select all elements  — but overall sum is not odd.

Example input:
5
1 1
999
1 1
1000
2 1
51 50
2 2
51 50
3 3
101 102 103

Example output:
Yes
No
Yes
Yes
No

Editorial:
Key Idea: The sum of $$$x$$$ numbers can only be odd if we have an odd number of numbers which are odd. (An odd statement, indeed).
Detailed Explanation: We first maintain two variables, num_odd and num_even, representing the number of odd and even numbers in the array, respectively. We then iterate over the number of odd numbers we can choose; which are $$$1,3,5,...$$$ upto min(num_odd,x), and see if num_even $$$\geq x - i$$$ where $$$i$$$ is the number of odd numbers we have chosen.
Time complexity: $$$O(N)$$$
Valera and Antique Items
Contest: Codeforces Round 252 (Div. 2)
Difficulty rating: 1000
Tags: implementation

Valera is a collector. Once he wanted to expand his collection with exactly one antique item.

Valera knows n sellers of antiques, the i-th of them auctioned ki items. Currently the auction price of the j-th object of the i-th seller is sij. Valera gets on well with each of the n sellers. He is perfectly sure that if he outbids the current price of one of the items in the auction (in other words, offers the seller the money that is strictly greater than the current price of the item at the auction), the seller of the object will immediately sign a contract with him.

Unfortunately, Valera has only v units of money. Help him to determine which of the n sellers he can make a deal with.

Input format:
The first line contains two space-separated integers n, v (1 ≤ n ≤ 50; 104 ≤ v ≤ 106) — the number of sellers and the units of money the Valera has.

Then n lines follow. The i-th line first contains integer ki (1 ≤ ki ≤ 50) the number of items of the i-th seller. Then go ki space-separated integers si1, si2, ..., siki (104 ≤ sij ≤ 106) — the current prices of the items of the i-th seller.

Output format:
In the first line, print integer p — the number of sellers with who Valera can make a deal.

In the second line print p space-separated integers q1, q2, ..., qp (1 ≤ qi ≤ n) — the numbers of the sellers with who Valera can make a deal. Print the numbers of the sellers in the increasing order.

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

Note:
In the first sample Valera can bargain with each of the sellers. He can outbid the following items: a 40000 item from the first seller, a 20000 item from the second seller, and a 10000 item from the third seller.

In the second sample Valera can not make a deal with any of the sellers, as the prices of all items in the auction too big for him.

Example input:
3 50000
1 40000
2 20000 60000
3 10000 70000 190000

Example output:
3
1 2 3

Example input:
3 50000
1 50000
3 100000 120000 110000
3 120000 110000 120000

Example output:
0

Editorial:
Valera and Fruits
Contest: Codeforces Round 252 (Div. 2)
Difficulty rating: 1400
Tags: greedy, implementation

Valera loves his garden, where n fruit trees grow.

This year he will enjoy a great harvest! On the i-th tree bi fruit grow, they will ripen on a day number ai. Unfortunately, the fruit on the tree get withered, so they can only be collected on day ai and day ai + 1 (all fruits that are not collected in these two days, become unfit to eat).

Valera is not very fast, but there are some positive points. Valera is ready to work every day. In one day, Valera can collect no more than v fruits. The fruits may be either from the same tree, or from different ones. What is the maximum amount of fruit Valera can collect for all time, if he operates optimally well?

Input format:
The first line contains two space-separated integers n and v (1 ≤ n, v ≤ 3000) — the number of fruit trees in the garden and the number of fruits that Valera can collect in a day.

Next n lines contain the description of trees in the garden. The i-th line contains two space-separated integers ai and bi (1 ≤ ai, bi ≤ 3000) — the day the fruits ripen on the i-th tree and the number of fruits on the i-th tree.

Output format:
Print a single integer — the maximum number of fruit that Valera can collect.

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

Note:
In the first sample, in order to obtain the optimal answer, you should act as follows.

- On the first day collect 3 fruits from the 1-st tree.
- On the second day collect 1 fruit from the 2-nd tree and 2 fruits from the 1-st tree.
- On the third day collect the remaining fruits from the 2-nd tree.

In the second sample, you can only collect 60 fruits, the remaining fruit will simply wither.

Example input:
2 3
1 5
2 3

Example output:
8

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

Example output:
60

Editorial:
Valera and Tubes
Contest: Codeforces Round 252 (Div. 2)
Difficulty rating: 1500
Tags: constructive algorithms, dfs and similar, implementation

Valera has got a rectangle table consisting of n rows and m columns. Valera numbered the table rows starting from one, from top to bottom and the columns – starting from one, from left to right. We will represent cell that is on the intersection of row x and column y by a pair of integers (x, y).

Valera wants to place exactly k tubes on his rectangle table. A tube is such sequence of table cells (x1, y1), (x2, y2), ..., (xr, yr), that:

- r ≥ 2;
- for any integer i (1 ≤ i ≤ r - 1) the following equation |xi - xi + 1| + |yi - yi + 1| = 1 holds;
- each table cell, which belongs to the tube, must occur exactly once in the sequence.

Valera thinks that the tubes are arranged in a fancy manner if the following conditions are fulfilled:

- no pair of tubes has common cells;
- each cell of the table belongs to some tube.

Help Valera to arrange k tubes on his rectangle table in a fancy manner.

Input format:
The first line contains three space-separated integers n, m, k (2 ≤ n, m ≤ 300; 2 ≤ 2k ≤ n·m) — the number of rows, the number of columns and the number of tubes, correspondingly.

Output format:
Print k lines. In the i-th line print the description of the i-th tube: first print integer ri (the number of tube cells), then print 2ri integers xi1, yi1, xi2, yi2, ..., xiri, yiri (the sequence of table cells).

If there are multiple solutions, you can print any of them. It is guaranteed that at least one solution exists.

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

Note:
Picture for the first sample:

Picture for the second sample:

Example input:
3 3 3

Example output:
3 1 1 1 2 1 3
3 2 1 2 2 2 3
3 3 1 3 2 3 3

Example input:
2 3 1

Example output:
6 1 1 1 2 1 3 2 3 2 2 2 1

Editorial:
Valera and Swaps
Contest: Codeforces Round 252 (Div. 2)
Difficulty rating: 2100
Tags: constructive algorithms, dsu, graphs, implementation, math, string suffix structures

A permutation p of length n is a sequence of distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n). A permutation is an identity permutation, if for any i the following equation holds pi = i.

A swap (i, j) is the operation that swaps elements pi and pj in the permutation. Let's assume that f(p) is the minimum number of swaps that you need to make the permutation p an identity permutation.

Valera wonders, how he can transform permutation p into any permutation q, such that f(q) = m, using the minimum number of swaps. Help him do that.

Input format:
The first line contains integer n (1 ≤ n ≤ 3000) — the length of permutation p. The second line contains n distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n) — Valera's initial permutation. The last line contains integer m (0 ≤ m < n).

Output format:
In the first line, print integer k — the minimum number of swaps.

In the second line, print 2k integers x1, x2, ..., x2k — the description of the swap sequence. The printed numbers show that you need to consecutively make swaps (x1, x2), (x3, x4), ..., (x2k - 1, x2k).

If there are multiple sequence swaps of the minimum length, print the lexicographically minimum one.

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

Note:
Sequence x1, x2, ..., xs is lexicographically smaller than sequence y1, y2, ..., ys, if there is such integer r (1 ≤ r ≤ s), that x1 = y1, x2 = y2, ..., xr - 1 = yr - 1 and xr < yr.

Example input:
5
1 2 3 4 5
2

Example output:
2
1 2 1 3

Example input:
5
2 1 4 5 3
2

Example output:
1
1 2

Editorial:
Valera and Number
Contest: Codeforces Round 252 (Div. 2)
Difficulty rating: 2400
Tags: bitmasks, dp, math, probabilities

Valera is a coder. Recently he wrote a funny program. The pseudo code for this program is given below:

Now Valera wonders: given the values x, k and p, what is the expected value of the resulting number s?

Input format:
The first line of the input contains three integers x, k, p (1 ≤ x ≤ 109; 1 ≤ k ≤ 200; 0 ≤ p ≤ 100).

Output format:
Print the required expected value. Your answer will be considered correct if the absolute or relative error doesn't exceed 10 - 6.

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

Note:
If the concept of expected value is new to you, you can read about it by the link:

http://en.wikipedia.org/wiki/Expected_value

Example input:
1 1 50

Example output:
1.0000000000000

Example input:
5 3 0

Example output:
3.0000000000000

Editorial:
Co-prime Array
Contest: Educational Codeforces Round 11
Difficulty rating: 1200
Tags: greedy, implementation, math, number theory

You are given an array of n elements, you must make it a co-prime array in as few moves as possible.

In each move you can insert any positive integral number you want not greater than 109 in any place in the array.

An array is co-prime if any two adjacent numbers of it are co-prime.

In the number theory, two integers a and b are said to be co-prime if the only positive integer that divides both of them is 1.

Input format:
The first line contains integer n (1 ≤ n ≤ 1000) — the number of elements in the given array.

The second line contains n integers ai (1 ≤ ai ≤ 109) — the elements of the array a.

Output format:
Print integer k on the first line — the least number of elements needed to add to the array a to make it co-prime.

The second line should contain n + k integers aj — the elements of the array a after adding k elements to it. Note that the new array should be co-prime, so any two adjacent values should be co-prime. Also the new array should be got from the original array a by adding k elements to it.

If there are multiple answers you can print any one of them.

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

Example input:
3
2 7 28

Example output:
1
2 7 9 28

Editorial:
Seating On Bus
Contest: Educational Codeforces Round 11
Difficulty rating: 1000
Tags: implementation

Consider 2n rows of the seats in a bus. n rows of the seats on the left and n rows of the seats on the right. Each row can be filled by two people. So the total capacity of the bus is 4n.

Consider that m (m ≤ 4n) people occupy the seats in the bus. The passengers entering the bus are numbered from 1 to m (in the order of their entering the bus). The pattern of the seat occupation is as below:

1-st row left window seat, 1-st row right window seat, 2-nd row left window seat, 2-nd row right window seat, ... , n-th row left window seat, n-th row right window seat.

After occupying all the window seats (for m > 2n) the non-window seats are occupied:

1-st row left non-window seat, 1-st row right non-window seat, ... , n-th row left non-window seat, n-th row right non-window seat.

All the passengers go to a single final destination. In the final destination, the passengers get off in the given order.

1-st row left non-window seat, 1-st row left window seat, 1-st row right non-window seat, 1-st row right window seat, ... , n-th row left non-window seat, n-th row left window seat, n-th row right non-window seat, n-th row right window seat.

The seating for n = 9 and m = 36.

You are given the values n and m. Output m numbers from 1 to m, the order in which the passengers will get off the bus.

Input format:
The only line contains two integers, n and m (1 ≤ n ≤ 100, 1 ≤ m ≤ 4n) — the number of pairs of rows and the number of passengers.

Output format:
Print m distinct integers from 1 to m — the order in which the passengers will get off the bus.

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

Example input:
2 7

Example output:
5 1 6 2 7 3 4

Example input:
9 36

Example output:
19 1 20 2 21 3 22 4 23 5 24 6 25 7 26 8 27 9 28 10 29 11 30 12 31 13 32 14 33 15 34 16 35 17 36 18

Editorial: