Mr. Hatter has $$$N$$$ strands of noodles, and wants to prepare some number of noodle dishes for his lunch party. The $$$i^{th}$$$ strand has flavor level $$$f_i$$$.
Each dish must have at least $$$K$$$ strands of noodles. The flavor of a dish is the maximum flavor value out of the noodle strands in the dish.
Mr. Hatter wants to know what is the maximum sum of flavors across all dishes he can prepare, assuming he prepares the dishes optimally?
The first line of input contains $$$N, K$$$, the total number of noodle strands and the number of strands of noodles required to make a dish. $$$(1 \leq N \leq 10^5$$$ and $$$1 \leq K \leq N)$$$
The next $$$N$$$ lines each contain $$$f_i$$$, the flavor value of the $$$i^{th}$$$ noodle strand. $$$(0 \leq f_i \leq 10^9)$$$
Please output $$$1$$$ integer, the maximum sum of flavors across all dishes Mr. Hatter can prepare.
2 1 76 100
176
4 2 1 5 3 1
8
9 3 10 9 9 9 9 1 1 1 1
28
After eating a bunch of noodles, the mad hatters decide that it's time to play a quick game of chess. They play a special variant of chess where the board is completely empty except for a single knight. Furthermore, they decide that this game is too boring, so they want to play on arbitrary-sized square chess boards, not just $$$8 \times 8$$$.
Given a chess board of size $$$N \times N$$$, and a knight starting at position $$$(x_1, y_1)$$$, how many steps at minimum would it take for it to reach position $$$(x_2, y_2)$$$?
If the position is not reachable, output $$$-1$$$.
Constraints:
$$$0 \lt N \lt 800$$$
$$$0 \lt x_i, y_i \lt N$$$
The first line of the input will contain just one number, N. The second line will contain two integers, $$$x_1$$$ and $$$y_1$$$, the starting position of the knight. The third line will contain three integers $$$x_2$$$ and $$$y_2$$$, the end position of the knight.
The output will consist of a single integer, which is the minimum number of moves the knight needs to make to reach the end position.
If the position is not reachable, output -1.
1 0 0 0 0
0
4 1 2 2 2
3
9 8 2 4 1
3
The Mad Hatter has moved past unsolvable riddles, and is now dabbling in unsolvable ciphers. On your recent trip through the looking-glass, he has presented you with a set of $$$N$$$ ciphers (which he has no idea how to solve). A cipher of length $$$s_i$$$ is a permutation of the integers $$$1..s_i$$$.
We consider a cipher solved if it is in ascending order. We can also perform an arbitrary number of rotations on these ciphers, in which we take the last element and move it to the front of the cipher. For example, here is a demonstration of how to solve this cipher:
- Original cipher: $$$[3, 4, 1, 2]$$$
- One rotation: $$$[2, 3, 4, 1]$$$
- Two rotations: $$$[1, 2, 3, 4]$$$, which is now in ascending order, so this cipher is solved.
However, these looking-glass ciphers have a special property: each cipher is entangled with another cipher, such that rotations performed on the first cipher will automatically be applied to the other cipher! Luckily, you've brought your looking-glass snare wand, which allows you to choose how to entangle the ciphers. Specifically, every cipher must be entangled with exactly one other cipher.
After you have entangled all ciphers, you will proceed to solve as many ciphers as you can by performing rotations on each pair of entangled ciphers. How many ciphers can you solve, if you entangle the ciphers optimally?
This is the easy version of this problem. The only difference between the two versions are the constraints on the input. In this version, $$$N \le 10^3$$$, and $$$s_1 = s_2 = ... = s_N \le 10^3$$$ (all ciphers are the same length).
The first line of input will contain a single integer $$$N$$$ denoting the number of ciphers. It is guaranteed that $$$N$$$ is even. ($$$2 \le N \le 10^3$$$)
The next $$$N$$$ lines represent the ciphers, permutations of length $$$s_1,...,s_N$$$. ($$$1 \le s_i \le 10^3$$$) Each line contains $$$s_i$$$ (the length of the permutation), followed by the permutation itself. In this version, $$$s_1 = s_2 = ... = s_N$$$.
Output a single integer, the number of ciphers you can solve if you provide an optimal initial entanglement.
4 4 1 4 2 3 4 3 4 1 2 4 2 3 4 1 4 2 3 4 1
3
You are given a noodle with a length of $$$0$$$ at time $$$t = 0$$$ seconds. Every second, the noodle will either grow or shrink by $$$1$$$. The noodle does this for $$$T$$$ seconds. A noodle can have negative length.
Calculate the number of ways that the maximum length of the noodle for times $$$0\leq t\leq T$$$ is exactly $$$M$$$. Output this $$$\text{mod}\: 10^9 + 7$$$.
The first line contains $$$N (1\leq N\leq 10^5)$$$, the number of test cases.
Then, each of the next $$$N$$$ lines will contain two numbers, $$$T (1\leq T\leq 2000)$$$, the time that the noodle can either grow or shrink, and $$$M(1\leq T\leq 2000)$$$, the maximum length of the noodle.
For each of the $$$N$$$ lines, output the number of ways that the maximum length of the noodle for times $$$0\leq t\leq T$$$ is exactly $$$M$$$ on a new line.
3 1 1 4 2 6 3
1 4 6
For the first case, we can achieve maximum of $$$1$$$ using. $$$(0, 1)$$$
For the second test case: $$$(0, 1, 2, 1, 0), (0, 1, 2, 1, 2), (0, -1, 0, 1, 2), (0, 1, 0, 1, 2)$$$.
For the third test case: $$$(0, 1, 2, 3, 2, 3, 2), (0, 1, 2, 3, 2, 1, 2), (0, 1, 2, 3, 2, 1, 0), (0, 1, 2, 1, 2, 3, 2), (0, -1, 0, 1, 2, 3, 2), (0, 1, 0, 1, 2, 3, 2)$$$
The infamous hat-wearing pasta-making brothers, Lario and Muigi, have decided to settle their rivalry once and for all with a game of wits – and spaghetti.
The game works as follows: Lario and Muigi take turns modifying a pile of spaghetti.
Lario goes first. Lario can make $$$n$$$ different types of spaghetti bundles, where the $$$i$$$th type of bundle contains $$$a_i$$$ strands of spaghetti. On his turn, Lario can choose a type of spaghetti bundle to make, adding $$$a_i$$$ strands to it.
Muigi is trying to assemble his own $$$m$$$ types of spaghetti bundles, where the $$$j$$$th type of bundle contains $$$b_j$$$ strands of spaghetti. On his turn, Muigi can take $$$b_j$$$ strands from the pile to assemble a spaghetti bundle of his own, as long as the pile has at least $$$b_j$$$ strands to begin with.
Note that either brother can choose to skip their turn by adding or removing $$$0$$$ strands from the pile.
The game lasts 100 rounds. If Lario can get the pile to have at least $$$t$$$ strands of spaghetti in that time, then he wins the spaghetti game. Otherwise, Muigi wins, having successfully stopped Lario.
Here's where you come in: You are the maddest hatter, and have the ability to mind control anyone wearing a hat. You don't really care which brother comes out on top, but you do love chaos and winning. In fact, you're set on taking over one of Lario and Muigi, and leading them to victory. Are you up to the task?
Note that this is an interactive problem, which has different input / output format. Read below for details.
The first line of input contains three integers, $$$n$$$, $$$m$$$, and $$$t$$$ ($$$1 \leq n, m, t \leq 100$$$). $$$n$$$ and $$$m$$$ are the number of Lario's bundles and Muigi's bundles, respectively. $$$t$$$ is the number of strands in the pile for Lario to win.
The second line contains $$$n$$$ integers, $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 100$$$), representing the number of strands in each of Lario's bundles.
The third line contains $$$m$$$ integers, $$$b_1, \ldots, b_m$$$ ($$$1 \leq b_j \leq 100$$$), representing the number of strands in each of Muigi's bundles.
Afterwards, your program should output either "Lario" or "Muigi", depending on which brother you would like to take control of. To pass the test case, you must win as your chosen brother.
Then, you will play the spaghetti game with the judge. When it is your turn, you must output a single integer on its own line; if you are Lario, it must be some $$$a_i$$$ (or $$$0$$$), and if you are Muigi, it must be some $$$b_j$$$ (or $$$0$$$). Otherwise, you will receive Wrong Answer as a verdict. When it is the judges turn, they will output one of $$$a_i$$$ (or $$$0$$$) if they are Lario, or one of $$$b_j$$$ (or $$$0$$$) if they are Muigi.
The game will automatically end once the pile has at least $$$t$$$ strands, or 100 rounds have passed (that is, both Lario and Muigi have each taken 100 actions). Your program should terminate once this happens, otherwise you may get undefined verdicts.
Remember to flush your output after printing each move. This can be done with cout.flush() in C++, System.out.flush() in Java, and stdout.flush() in Python.
3 3 20 3 6 15 2 8 15 0 8 2
Lario 6 6 3 15
In this example, you control Lario. The game plays as follows:
- Lario adds 6 strands to the pile. The pile has 6 strands of spaghetti.
- Muigi skips his turn. The pile has 6 strands of spaghetti.
- Lario adds 6 strands to the pile. The pile has 12 strands of spaghetti.
- Muigi removes 8 strands from the pile. The pile has 4 strands of spaghetti.
- Lario adds 3 strands to the pile. The pile has 7 strands of spaghetti.
- Muigi removes 2 strands from the pile. The pile has 5 strands of spaghetti.
- Lario adds 15 strands from the pile. The pile has 20 strands of spaghetti, so Lario wins.
Just kidding! This problem isn't actually about eertree's.
Alice was eating a bowl of alphabet soup when she was magically transported to Wonderland! There she met the Mad Hatter who had a most devious plan in mind. While Alice was busy recovering from the existential crisis of being teleported to a new realm, the Hatter stole all $$$N$$$ of the letter-shaped noodles from Alice's alphabet soup and gave them to the Cheshire Cat.
Curiously, the Cheshire Cat lives in a tree consisting of $$$N$$$ nodes and $$$N - 1$$$ branches such that the set of nodes is connected when the branches are though of as undirected edges, and there exists a unique shortest path between any pair of nodes (hence the tree is in fact a tree). The evil Cheshire Cat takes each of the noodle letters and places them in a different node of the tree such that each node has exactly one letter associated with it (if there are duplicate letters, multiple nodes may be assigned the same letter, but no node will be left without a letter).
The Mad Hatter now gives Alice a contrived puzzle, stating that she can only win her soup back if she solves it! Specifically, the Hatter wants Alice to figure out for each node $$$u$$$, if the tree was rooted at $$$u$$$, how many non-empty subtrees of the tree would be able to have their associated letters rearranged into a palindrome?
Note that a subtree in a rooted tree is a node along with all of its descendants. A palindrome is a word which is the same forwards and backwards. More formally, a string $$$s = s_1s_2\dots s_l$$$ is a palindrome if $$$s_i = s_{l-i+1}$$$ for all $$$i \in \{1, 2, \dots, l\}$$$.
Given the structure of the Cheshire Cat's tree and the arrangement of the letter-shaped noodles across the nodes, can you help Alice figure out the Hatter's riddle and help her get her noodle soup back?
The input will begin with a line containing a single positive integer $$$N\ (1 \leq N \leq 2 \cdot 10^5)$$$, denoting both the number of noodle letters in Alice's noodle soup as well as the number of nodes in the Cheshire Cat's tree.
The next line will contain a string of $$$N$$$ uppercase English letters $$$s_1s_2\dots s_N$$$. The $$$i$$$th letter, $$$s_i$$$, will be placed in the $$$i$$$th node of the Cheshire Cat's tree.
The final $$$N - 1$$$ lines of input will each contain two space-separated integers $$$u,\ v\ (1 \leq u, v \leq N,\ u \neq v)$$$ denoting a branch (edge) between the $$$u$$$th and $$$v$$$th nodes in the tree. It is guaranteed that these edges will form a tree.
The output should consist of $$$N$$$ lines, each containing a single nonnegative integer. In particular, the $$$i$$$th line of output should contain the number of non-empty subtrees of the tree which would be able to have their associated letters rearranged into a palindrome if the tree was rooted at the $$$i$$$th node.
4 HELP 1 2 2 4 3 4
1 2 1 2
5 AAAAA 1 2 2 3 3 4 4 5
5 5 5 5 5
In the first sample, the tree looks something like this:
In this case, regardless of the rooting of the tree, the only subtrees which can have their letters rearranged into palindromes are the leaves of the tree.
In the second sample, the tree looks something like this:
In this case, every letter is the same, so every subtree can have its letters rearranged into palindromes regardless of the rooting of the tree.
In both cases, the nodes are labeled with the letter they are assigned as well as their node number to avoid ambiguity.
The Mad Hatter has moved past unsolvable riddles, and is now dabbling in unsolvable ciphers. On your recent trip through the looking-glass, he has presented you with a set of $$$N$$$ ciphers (which he has no idea how to solve). A cipher of length $$$s_i$$$ is a permutation of the integers $$$1..s_i$$$.
We consider a cipher solved if it is in ascending order. We can also perform an arbitrary number of rotations on these ciphers, in which we take the last element and move it to the front of the cipher. For example, here is a demonstration of how to solve this cipher:
- Original cipher: $$$[3, 4, 1, 2]$$$
- One rotation: $$$[2, 3, 4, 1]$$$
- Two rotations: $$$[1, 2, 3, 4]$$$, which is now in ascending order, so this cipher is solved.
However, these looking-glass ciphers have a special property: each cipher is entangled with another cipher, such that rotations performed on the first cipher will automatically be applied to the other cipher! Luckily, you've brought your looking-glass snare wand, which allows you to choose how to entangle the ciphers. Specifically, every cipher must be entangled with exactly one other cipher.
After you have entangled all ciphers, you will proceed to solve as many ciphers as you can by performing rotations on each pair of entangled ciphers. How many ciphers can you solve, if you entangle the ciphers optimally?
This is the hard version of this problem. The only difference between the two versions are the constraints on the input. In this version, $$$N \le 100$$$, and there are no restrictions on each $$$s_i$$$, except that $$$1 \le s_i \le 10^3$$$).
The first line of input will contain a single integer $$$N$$$ denoting the number of ciphers. It is guaranteed that $$$N$$$ is even. ($$$2 \le N \le 100$$$)
The next $$$N$$$ lines represent the ciphers, permutations of length $$$s_1,...,s_N$$$. ($$$1 \le s_i \le 10^3$$$) Each line contains $$$s_i$$$ (the length of the permutation), followed by the permutation itself.
Output a single integer, the number of ciphers you can solve if you provide an optimal initial entanglement.
4 4 1 4 2 3 4 3 4 1 2 4 2 3 4 1 4 2 3 4 1
3
4 6 1 2 5 6 4 3 6 6 1 2 3 4 5 8 5 6 7 8 1 2 3 4 4 1 2 3 4
3