There are $$$n$$$ ingredients, numbered from $$$1$$$ to $$$n$$$. The quality of the $$$i$$$th ingredient is $$$a_i$$$.
A dish consists of some nonempty set of ingredients. If a dish contains ingredients with qualities $$$b_1, b_2, ..., b_k$$$, the quality of the dish is $$$\sum\limits_{i=1}^k b_i + \max\limits_{1\leq i\leq k} b_i$$$.
Among all ways to partition the $$$n$$$ ingredients into $$$k$$$ dishes, what is the maximum possible sum of dish qualities? Each ingredient must belong to exactly one dish, and each dish must contain at least one ingredient.
The first line of input consists of two space-separated integers $$$n$$$ and $$$k$$$ $$$(1 \leq k \leq n \leq 2 \cdot 10^5)$$$.
The second line of input consists of $$$n$$$ space-separated integers $$$a_1, a_2, ..., a_n$$$ $$$(1 \leq a_i \leq 10^3)$$$.
On the first and only line, output the answer to the problem.
6 3 7 3 9 1 2 7
52
5 5 1 1 1 1 1
10
In the first sample test case, one optimal partition is:
- Dish $$$1$$$ contains ingredients $$$1$$$ and $$$2$$$ with qualities $$$7$$$ and $$$3$$$. The quality of the dish is $$$7 + 3 + \max(7, 3) = 17$$$.
- Dish $$$2$$$ contains ingredients $$$3$$$ and $$$5$$$ with qualities $$$9$$$ and $$$2$$$. The quality of the dish is $$$9 + 2 + \max(9, 2) = 20$$$.
- Dish $$$3$$$ contains ingredients $$$4$$$ and $$$6$$$ with qualities $$$1$$$ and $$$7$$$. The quality of the dish is $$$1 + 7 + \max(1, 7) = 15$$$.
The sum of dish qualities is $$$17 + 20 + 15 = 52$$$. It can be proven that no larger sum is possible.
In the second sample test case, each ingredient must belong to a distinct dish. The sum of qualities is then $$$5 \cdot (1 + 1) = 10$$$.
You're in a field, which can be represented by $$$n + 1$$$ cells numbered from $$$0$$$ to $$$n$$$. The state of the field can be represented by a sequence of $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$. For all $$$i$$$, if $$$a_i \gt 0$$$, then cell $$$i$$$ contains a watermelon worth $$$a_i$$$ health. Otherwise, if $$$a_i = 0$$$, then cell $$$i$$$ is empty. Cell $$$0$$$ is always empty. Initially, you're located in cell $$$0$$$ and have $$$h$$$ health.
In each minute, the following will occur in order:
- Suppose you're in cell $$$i$$$. If $$$i \lt n$$$, you have the option to move to cell $$$i + 1$$$. If $$$i \gt 0$$$, you have the option to move to cell $$$i - 1$$$. You must pick an option. Let $$$j$$$ be the new cell you move to.
- If cell $$$j$$$ contains a watermelon, you eat it and $$$h$$$ increases by $$$a_j$$$. The watermelon disappears and $$$a_j$$$ becomes $$$0$$$.
- $$$h$$$ decreases by $$$1$$$. If $$$h = 0$$$, then you starve.
- The health value of all uneaten watermelons increases by $$$1$$$. In other words, for all $$$k$$$ such that $$$a_k \gt 0$$$, $$$a_k$$$ increases by $$$1$$$.
Please determine if it's possible for you to reach cell $$$n$$$ without starving. It doesn't count if you starve in the last minute.
The first line of input consists of two space-separated integers $$$n$$$ and $$$h$$$ $$$(1 \leq n, h \leq 2 \cdot 10^5)$$$.
The second line of input consists of $$$n$$$ space-separated integers $$$a_1, a_2, ..., a_n$$$ $$$(0 \leq a_i \leq 2 \cdot 10^5)$$$.
On the first and only line, output YES if it's possible for you to reach cell $$$n$$$ without starving. Otherwise, output NO.
10 3 1 1 1 0 0 0 0 0 0 0
YES
11 3 1 1 1 0 0 0 0 0 0 0 0
NO
1 1 1
YES
One possible path to cell $$$n$$$ for the first sample test case looks like this:
It can be proven that it is impossible to reach cell $$$n$$$ without starving in the second test case.
Columbia University has created a new song in honor of itself, which can be represented as a string $$$s_1s_2...s_n$$$. As a Columbia-hater, this string makes you incredibly angry, so you decide to desecrate it by performing the following operation:
You select a nonempty integer sequence $$$i_1, i_2, ..., i_k$$$ such that $$$1 \leq i_1 \lt i_2 \lt ... \lt i_k \leq n$$$, and create a new string $$$t$$$ as follows: initially all of the characters of $$$t$$$ are the same as $$$s$$$. Then, for all $$$1 \leq j \leq k$$$, you set $$$t_{i_j}$$$ to be $$$s_{i_{k - j + 1}}$$$. In other words, $$$t$$$ is the same as $$$s$$$, but with the characters at positions $$$i_1, i_2, ..., i_k$$$ reversed.
Your objective is to select $$$i_1, i_2, ..., i_k$$$ such that $$$t$$$ does not contain the string columbia as a subsequence. Please find any $$$i_1, i_2, ..., i_k$$$ that satisfies this, or report that it is impossible.
A subsequence of a string $$$s$$$ is defined as any new string that can be obtained from the deletion of zero or more characters from $$$s$$$ and concatenating the remaining parts. For example, columbia is a subsequence of cxoxlxuxmxbxixa.
The first and only line consists of a single string $$$s_1s_2...s_n$$$ $$$(1 \leq n \leq 2 \cdot 10^5)$$$. All $$$s_i$$$ will be lowercase letters from the English alphabet.
If it is possible to pick an integer sequence $$$i_1, i_2, ..., i_k$$$ that satisfies the constraints of the problem, output any such sequence as follows: on the first line, output a single integer $$$k$$$ $$$(1 \leq k \leq n)$$$ describing the length of the sequence. On the second line, output $$$k$$$ space-separated integers $$$i_1, i_2, ..., i_k$$$ $$$(1 \leq i_1 \lt i_2 \lt ... \lt i_k \leq n)$$$.
Otherwise, if no such sequence exists, output a single line with the string NO.
cxoxlxuxmxbxixa
3 1 2 3
columbiaisthebestschoolevercolumbiakidsarekindandclever
6 1 30 31 32 33 34
wellstaynumberoneforever
1 1
In the first sample test case, the characters at positions $$$1, 2, 3$$$ are reversed. The string becomes oxcxlxuxmxbxixa, which does not contain columbia as a subsequence.
In the second sample, the new song is iolumbiaisthebestschoolevercobmulcakidsarekindandclever. I think the song is greatly improved this way!
In the third sample, the string doesn't even have the letter c in it, so any valid output is a valid solution.
You are given a drawing on the XY-coordinate plane consisting of $$$a + b$$$ infinitely long lines and $$$c$$$ non-overlapping rectangles. $$$a$$$ of the lines are parallel to the x-axis, and $$$b$$$ of them are parallel to the y-axis. The lines and rectangles in this drawing partition the plane into some finite number of regions.
A coloring of the drawing is an assignment of a single color to each region. A coloring is considered valid if no two adjacent regions share the same color. Two regions are adjacent if there are infinitely many points in the intersection of their borders. In other words, the regions must be next to each other, and share more than a corner.
A coloring statement is a sequence of integers $$$k, s_1, s_2, ..., s_k$$$. A coloring statement is considered valid if there exists a coloring of the drawing that uses $$$k$$$ colors, has $$$s_1$$$ regions colored using the first color, has $$$s_2$$$ regions colored using the second color, and so on.
Your task is to find the lexicographically smallest valid coloring statement.
A sequence $$$a_1, a_2, ..., a_n$$$ is lexicographically smaller than another sequence $$$b_1, b_2, ..., b_m$$$ if either $$$n \lt m$$$ and $$$a_i = b_i$$$ for all $$$1 \leq i \leq n$$$, or if there exists an $$$i$$$ such that $$$a_i \lt b_i$$$ and $$$a_j = b_j$$$ for all $$$j \lt i$$$.
The first line of input consists of three space-separated integers $$$a$$$, $$$b$$$, and $$$c$$$ $$$(1 \leq a, b, c \leq 10^5)$$$.
The second line of input consists of $$$a$$$ space-separated integers $$$y_1, y_2, ..., y_a$$$ $$$(-10^9 \leq y_i \leq 10^9)$$$. These values represent the y-coordinates of the lines parallel to the x-axis.
The third line of input consists of $$$b$$$ space-separated integers $$$x_1, x_2, ..., x_b$$$ $$$(-10^9 \leq x_i \leq 10^9)$$$. These values represent the x-coordinates of the lines parallel to the y-axis.
The following $$$c$$$ lines each consist of four space-separated integers $$$x_1, y_1, x_2, y_2$$$ $$$(-10^9 \leq x_1 \lt x_2 \leq 10^9, -10^9 \leq y_1 \lt y_2 \leq 10^9)$$$ describing each rectangle. $$$(x_1, y_1)$$$ are the coordinates of the bottom-left corner of the rectangle, and $$$(x_2, y_2)$$$ are the coordinates of the top-right corner.
Every rectangle has at least one horizontal and vertical line passing through it. Among any two rectangles, the intersection of their areas, including borders, is empty.
It is guaranteed that all of the x-coordinates among all objects are distinct. The same is true for all of the y-coordinates.
On the first and only line, output an integer $$$k$$$, followed by a space, followed by $$$k$$$ space-separated integers $$$s_1, s_2, ..., s_k$$$.
1 1 1 0 0 -1 -1 1 1
2 4 4
2 2 1 -1 1 -1 1 -2 -2 2 2
2 8 9
The first sample test case can be colored as shown in following figure:
It uses $$$2$$$ colors, has $$$4$$$ regions colored orange, and another $$$4$$$ regions colored blue. It can be proven that no fewer colors than $$$2$$$ colors can be used, and that if $$$2$$$ colors are used, any color must be used at least $$$4$$$ times.
One solution to the second sample test case looks like this:
You are given $$$n$$$ cards $$$c_1, c_2, ..., c_n$$$ arranged in a row. Some of the cards are lying face-up, and some of them are face-down. Flipping a face-up card makes it face-down, and vice versa. In one operation, you may select any face-up card $$$c_i$$$, and flip it along with all cards to the right of it. In other words, you may select any card $$$c_i$$$ that is face up, and flip all cards $$$c_j$$$ such that $$$j \geq i$$$.
It can be shown that the maximum number of operations you can possibly perform until it becomes impossible to do so is finite. Please find and output this number.
Since this number might be large, please output it modulo $$$10^9 + 7$$$.
The first and only line of input consists of a single string $$$c_1c_2...c_n$$$ $$$(1 \leq n \leq 2 \cdot 10^5)$$$. If $$$c_i$$$ is O, the $$$i$$$th card is face-up. Otherwise, $$$c_i$$$ will be X, representing a face-down card.
On the first and only line, output the answer to the problem, modulo $$$10^9 + 7$$$.
XXOXO
5
XXXXXX
0
OXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
294967268
In the first sample test case, one maximum-length sequence of operations is:
$$$$$$\tt{XXOXO} \rightarrow \tt{XXOX\color{red}{X}} \rightarrow \tt{XX\color{red}{XOO}} \rightarrow \tt{XXXO\color{red}{X}} \rightarrow \tt{XXX\color{red}{XO}} \rightarrow \tt{XXXX\color{red}{X}}$$$$$$
The red characters represent which cards have been flipped.
In the second sample, no operations are possible to perform on the initial sequence of cards, so the answer is $$$0$$$.
You are given an integer array $$$a_1, a_2, ..., a_n$$$, and two integers $$$k$$$ and $$$q$$$. Please answer the following $$$q$$$ queries:
For each query, you are given two integers $$$l$$$ and $$$r$$$. Your task is to determine whether there exists a nonempty subset of $$$\{a_l, a_{l + 1}, ..., a_r\}$$$ whose bitwise AND is equal to exactly $$$k$$$.
We define the bitwise AND of a nonempty integer subset $$$\{b_1, b_2, ..., b_m\}$$$ to be $$$b_1$$$ if $$$m = 1$$$, and $$$b_1 \text{ AND } b_2 \text{ AND } ... \text{ AND } b_m$$$ otherwise.
The first line of input consists of three space-separated integers $$$n$$$, $$$k$$$, and $$$q$$$ $$$(1 \leq n, q \leq 2 \cdot 10^5$$$, $$$0 \leq k \lt 2^{30})$$$.
The second line consists of $$$n$$$ space-separated integers $$$a_1, a_2, ..., a_n$$$ $$$(0 \leq a_i \lt 2^{30})$$$.
The next $$$q$$$ lines each consist of two space-separated integers $$$l$$$ and $$$r$$$ $$$(1 \leq l \leq r \leq n)$$$.
Output $$$q$$$ lines. On the $$$i$$$th line, output YES if the answer to the $$$i$$$th query is yes, and NO otherwise.
5 2 3 1 6 10 0 2 1 3 1 2 3 5
YES NO YES
10 2 10 2 10 6 8 14 7 13 6 9 8 2 7 5 6 1 6 4 8 4 10 2 7 6 8 2 8 5 8 1 1
YES NO YES NO NO YES NO YES NO YES
In the first sample test case, the answer to the first query is YES, since $$$6 \text{ AND } 10 = 2$$$.
There is no nonempty subset of $$$\{1, 6\}$$$ with AND equal to $$$2$$$, so the answer to the second query is NO.
For the third query, the subset $$$\{2\}$$$ can be picked.
You are given an $$$n$$$-dimensional hypercube with side length $$$10^5$$$. The hypercube contains $$$(10^5)^n$$$ cells, each of which is labeled with a unique $$$n$$$-integer tuple $$$(p_1, p_2, ..., p_n)$$$ such that for all $$$i$$$, $$$1 \leq p_i \leq 10^5$$$. Additionally, each cell contains a single integer, which is initially set to $$$0$$$.
Your task is to process $$$q$$$ of the following two types of queries:
- ADD $$$(l_1, r_1), (l_2, r_2), ..., (l_n, r_n), x$$$: For all cells labelled $$$(p_1, p_2, ..., p_n)$$$ such that for all $$$i$$$, $$$l_i \leq p_i \leq r_i$$$, increment the value they each contain by $$$x$$$.
- SUM $$$(l_1, r_1), (l_2, r_2), ..., (l_n, r_n)$$$: Compute the sum of all integers held by cells labelled $$$(p_1, p_2, ..., p_n)$$$ such that for all $$$i$$$, $$$l_i \leq p_i \leq r_i$$$. Since the sum can be large, please output it modulo $$$998244353$$$.
It is guaranteed that for all queries, for all $$$i$$$, $$$l_i$$$ and $$$r_i$$$ have been picked uniformly at random from all $$$\binom{10^5 + 1}{2}$$$ possible choices.
The first line of input consists of two space-separated integers $$$n$$$ and $$$q$$$ $$$(1 \leq n \leq 500, 1 \leq q \leq 3000)$$$.
The next $$$q$$$ lines each consist of a query, which is described by one of the following:
- The string ADD followed by a space, followed by $$$2n + 1$$$ space-separated integers $$$l_1, r_1, l_2, r_2, ..., l_n, r_n, x$$$ $$$(1 \leq l_i \leq r_i \leq 10^5, 0 \leq x \lt 998244353)$$$.
- The string SUM followed by a space, followed by $$$2n$$$ space-separated integers $$$l_1, r_1, l_2, r_2, ..., l_n, r_n$$$ $$$(1 \leq l_i \leq r_i \leq 10^5)$$$.
It is guaranteed that for all queries, for all $$$i$$$, $$$l_i$$$ and $$$r_i$$$ have been picked uniformly at random from all $$$\binom{10^5 + 1}{2}$$$ possible choices.
If there are $$$k$$$ SUM queries, output $$$k$$$ lines. The $$$i$$$th line should contain the answer to the $$$i$$$th SUM query, modulo $$$998244353$$$.
1 5 SUM 80990 92828 ADD 73356 82192 15 SUM 4355 39641 ADD 10847 85692 67 SUM 10750 13698
0 0 191084
2 6 ADD 59731 94993 24909 93877 2273 SUM 26347 68751 34850 79984 ADD 7811 91704 14253 48118 12634 SUM 57180 64491 33935 67473 ADD 18494 42024 70782 71906 13972 ADD 65552 83196 57079 87722 7732
108608724 208434911
In the first sample test case, the answer to the first SUM query is $$$0$$$ since no ADD queries have occurred yet.
The answer to the second SUM query is also $$$0$$$, since no ADD queries have modified the values of the cells in that region.
The answer to the third SUM query is $$$(13698 - 10847 + 1) \cdot 67 = 191084$$$.
You are given a single integer $$$n$$$. Please output any permutation $$$p_1, p_2, ..., p_n$$$ such that for all $$$1 \leq i \lt n$$$, $$$p_i$$$ and $$$p_{i + 1}$$$ are coprime. Additionally, $$$p_1$$$ and $$$p_n$$$ must be coprime.
A permutation of length $$$n$$$ is a sequence of $$$n$$$ integers such that all integers between $$$1$$$ and $$$n$$$ inclusive appear in it exactly once.
Two integers are coprime if their greatest common divisor is equal to $$$1$$$.
It can be proven that such a permutation always exists.
The first and only line of input consists of a single integer $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^5)$$$.
On the first and only line, output $$$n$$$ space-separated integers $$$p_1, p_2, ..., p_n$$$ that satisfy the constraints of the problem.
If there are multiple solutions, you may output any such one.
5
4 1 2 5 3
2
1 2
In the first sample test case, the output is valid because $$$\gcd(4, 1) = \gcd(1, 2) = \gcd(2, 5) = \gcd(5, 3) = \gcd(4, 3) = 1$$$. There are other valid outputs for $$$n = 5$$$, for example $$$2, 3, 5, 4, 1$$$.
| Phebe found herself facing a difficult situation, hurt and betrayed by Ryan's actions. Ryan, aware of the gravity of his mistake, understood the immense challenge he faced in trying to salvage their relationship. Taking a deep breath, he approached Phebe, hoping to find the right words to convince her not to end things. "Phebe, I understand that I have hurt you deeply, and I'm truly sorry for my actions. I know I can't change the past, but please give me a chance to explain and work things out together." Phebe looked at Ryan with a mix of anger and sadness, unsure if she could trust him again. Ryan continued, his voice filled with sincerity and remorse. "Phebe, please write a computer program to solve the following problem." |
Among Phebe and Ryan is a pile of blocks, each weighing some integer number of kilograms. There is also a scale, initially reading zero kilograms. Phebe and Ryan take turns picking any block, and placing it on top of the scale (after which the reading on the scale increases by the weight of the block). The first player who either makes the scale read exactly $$$k$$$, or runs out of blocks to place, loses. Phebe makes the first move.
You are given an array of $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$. Please process $$$q$$$ of the following two types of queries:
- SET $$$i, x$$$: Set $$$a_i$$$ to $$$x$$$.
- ? $$$k$$$: Phebe and Ryan play the aforementioned game using $$$\sum a_i$$$ blocks. For all $$$1 \leq i \leq n$$$, there are $$$a_i$$$ blocks weighing $$$i$$$ kilograms. If the game uses the given parameter $$$k$$$, and both players play optimally, who will win?
The first line of input consists of two space-separated integers $$$n$$$ and $$$q$$$ $$$(1 \leq n, q \leq 2 \cdot 10^5)$$$.
The second line consists of $$$n$$$ space-separated integers $$$a_1, a_2, ..., a_n$$$ $$$(0 \leq a_i \leq 10^8)$$$.
The next $$$q$$$ lines each consist of a query, which is described by one of the following:
- The string SET followed by a space, followed by two space-separated integers $$$i$$$ and $$$x$$$ $$$(1 \leq i \leq n$$$, $$$0 \leq x \leq 10^8)$$$.
- The string ? followed by a space, followed by a single integer $$$k$$$ $$$(1 \leq k \leq 10^{18})$$$.
It is guaranteed that during any ? query, $$$\sum a_i \gt 0$$$.
If there are $$$k$$$ ? queries, output $$$k$$$ lines.
On the $$$i$$$th line, if Phebe will win the game under the conditions of the $$$i$$$th ? query, output the string PHEBE, otherwise output the string RYAN.
5 6 0 2 3 0 0 ? 10 SET 5 1 ? 10 SET 1 50 ? 37 ? 38
PHEBE RYAN RYAN PHEBE
6 10 1 1 1 1 1 1 ? 21 ? 31 SET 6 0 ? 5 SET 2 5 ? 17 ? 20 SET 3 10 ? 10 ? 1000000000000000000
PHEBE RYAN PHEBE PHEBE PHEBE RYAN RYAN
In the first query of the first sample test case, Phebe and Ryan play the game using $$$2$$$ blocks of weight $$$2$$$ and $$$3$$$ blocks of weight $$$3$$$. One possible game with both players playing optimally is the following:
- Phebe picks a block of weight $$$2$$$. The scale now reads $$$2$$$.
- Ryan picks a block of weight $$$3$$$. The scale now reads $$$5$$$.
- Phebe picks a block of weight $$$2$$$. The scale now reads $$$7$$$.
- Ryan is forced to pick a block of weight $$$3$$$. The scale now reads $$$10$$$ and Phebe wins.
After learning $$$10^{100}$$$ data structures, Nea1 has decided to return to China and become a farmer!
Nea1 has $$$n$$$ chickens, labeled from $$$1$$$ to $$$n$$$. The relationships among the chickens can be described by a forest with $$$n - 2$$$ edges, where edges represent incompatibility. In other words:
- There are $$$n - 2$$$ pairs of chickens that are incompatible.
- There do not exist distinct integers $$$c_1, c_2, ..., c_k$$$ such that $$$k \geq 3$$$, chickens $$$c_1$$$ and $$$c_k$$$ are incompatible, and chickens $$$c_i$$$ and $$$c_{i + 1}$$$ are incompatible for all $$$1 \leq i \lt k$$$.
- A chicken is never incompatible with itself, and all pairs are distinct.
Additionally, every chicken is incompatible with at least one other chicken.
Nea1 would like to cross a river using a rowboat that can hold at most $$$k$$$ chickens (along with himself) at once. Is it possible for him to bring all $$$n$$$ chickens across the river such that no two incompatible chickens are ever left unattended?
More formally, let $$$A$$$ and $$$B$$$ represent the sets of chickens on both sides of the river. Initially, $$$A = \{1, 2, ..., n\}$$$ and $$$B$$$ is the empty set. Nea1 can perform a sequence of operations. On the $$$i$$$th operation, he does the following:
- If $$$i$$$ is odd, he picks some subset $$$M \subseteq A$$$ such that $$$|M| \leq k$$$, and there do not exist $$$i, j \in A - M$$$ such that chickens $$$i$$$ and $$$j$$$ are incompatible. Afterwards, he sets $$$A$$$ to $$$A - M$$$ and sets $$$B$$$ to $$$B \cup M$$$. Note that afterwards, $$$B$$$ is allowed to contain integers representing incompatible chickens.
- If $$$i$$$ is even, he picks some subset $$$M \subseteq B$$$ such that $$$|M| \leq k$$$, and there do not exist $$$i, j \in B - M$$$ such that chickens $$$i$$$ and $$$j$$$ are incompatible. Afterwards, he sets $$$B$$$ to $$$B - M$$$ and sets $$$A$$$ to $$$A \cup M$$$. Note that afterwards, $$$A$$$ is allowed to contain integers representing incompatible chickens.
Does there exist any sequence of operations such that at the end, $$$A$$$ is the empty set and $$$B = \{1, 2, ..., n\}$$$? If so, output any sequence that accomplishes this.
The first line of input consists of two space-separated integers $$$n$$$ and $$$k$$$ $$$(4 \leq n \leq 1500, 1 \leq k \leq n)$$$.
The following $$$n - 2$$$ lines each consist of two space-separated integers $$$u$$$ and $$$v$$$ $$$(1 \leq u, v \leq n, u \neq v)$$$, representing incompatibility between chickens $$$u$$$ and $$$v$$$. It is guaranteed that the incompatibility graph is a forest, and that every chicken is incompatible with at least one other chicken.
If there exists some sequence of operations that results in all chickens crossing the river, output any such sequence as follows:
On the first line, output a single integer $$$o$$$ $$$(1 \leq o \leq 4000)$$$, representing the number of operations.
On each of the following $$$m$$$ lines, output a space-separated integer sequence $$$s, m_1, m_2, ..., m_s$$$ $$$(0 \leq s \leq k, 1 \leq m_i \leq n)$$$. On the $$$i$$$th line, $$$s$$$ should describe the size of the chosen subset $$$M$$$ used in the $$$i$$$th operation. All $$$m_i$$$ should be distinct and members of $$$M$$$.
Otherwise, if it is impossible for the chickens to cross the river, output a single line with the string NO.
It can be proven that if there exists any working sequence of operations, there also exists one with at most $$$4000$$$ operations under the constraints of the problem.
6 4 1 2 2 3 2 4 5 6
3 4 1 2 3 5 1 2 3 6 2 4
4 4 1 2 3 4
1 4 1 2 3 4
4 1 1 2 3 4
NO
In the first sample test case, the incompatibility graph looks as follows:
Here are 3 operations in one of the possible solutions:
In the second sample, all chickens can be moved to the other side in a single operation.
In the third sample, it can be proven that no solution exists.
In this task, you will have a choice between solving either of the following two problems:
Problem 1
Write a program that does anything you want.
However, you'll have to Venmo @askdfjlas $$$1$$$ dollar.
Problem 2
Write a program that outputs a few sentences complimenting askd, the author of this contest.
The input consists of a single ?.
Either output anything you want after Venmoing @askdfjlas $$$1$$$ dollar, or output a few sentences complimenting him.
?
askd is the coolest! his osu! play on Necro Fantasia by MISATO [Lasse's Lunatic] with the double time modification with 4 misses and 94.29% accuracy worth 420 performance points is one of the greatest feats ever accomplished by humankind. additionally, I legally owe him my life savings now.