Sichuan hotpot is one of the most famous dishes around the world. People love its spicy taste.
There are $$$n$$$ tourists, numbered from $$$0$$$ to $$$(n-1)$$$, sitting around a hotpot. There are $$$k$$$ types of ingredients for the hotpot in total and the $$$i$$$-th tourist favors ingredient $$$a_i$$$ most. Initially, every tourist has a happiness value of $$$0$$$ and the pot is empty.
The tourists will perform $$$m$$$ moves one after another, where the $$$i$$$-th (numbered from $$$0$$$ to $$$(m - 1)$$$) move is performed by tourist $$$(i \mod n)$$$. When tourist $$$t$$$ moves:
- If ingredient $$$a_t$$$ exists in the pot, he will eat them all and gain $$$1$$$ happiness value.
- Otherwise, he will put one unit of ingredient $$$a_t$$$ into the pot. His happiness value remains unchanged.
Your task is to calculate the happiness value for each tourist after $$$m$$$ moves.
There are multiple test cases. The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 10^3$$$) indicating the number of test cases. For each test case:
The first line contains three integers $$$n$$$, $$$k$$$ and $$$m$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le k \le 10^5$$$, $$$1 \le m \le 10^9$$$) indicating the number of tourists, the number of types of ingredients and the number of moves.
The second line contains $$$n$$$ integers $$$a_0, a_1, \cdots, a_{n-1}$$$ ($$$1 \le a_i \le k$$$) where $$$a_i$$$ indicates the favorite ingredient of tourist $$$i$$$.
It's guaranteed that neither the sum of $$$n$$$ nor the sum of $$$k$$$ of all the test cases will exceed $$$2 \times 10^5$$$.
For each test case output $$$n$$$ integers $$$h_0, h_1, \cdots, h_{n-1}$$$ in one line separated by a space, where $$$h_i$$$ indicates the happiness value of tourist $$$i$$$ after $$$m$$$ moves.
Please, DO NOT output extra spaces at the end of each line, or your answer might be considered incorrect!
4 3 2 6 1 1 2 1 1 5 1 2 2 10 1 2 2 2 10 1 1
0 2 1 2 2 2 0 5
The first sample test case is explained as follows:
| Move | Tourist | Action | Pot after move |
| 0 | 0 | Puts ingredient 1 into the pot | $$$\{1\}$$$ |
| 1 | 1 | Eats ingredient 1 in the pot | $$$\{\}$$$ |
| 2 | 2 | Puts ingredient 2 into the pot | $$$\{2\}$$$ |
| 3 | 0 | Puts ingredient 1 into the pot | $$$\{1, 2\}$$$ |
| 4 | 1 | Eats ingredient 1 in the pot | $$$\{2\}$$$ |
| 5 | 2 | Eats ingredient 2 in the pot | $$$\{\}$$$ |
There are $$$n$$$ ants living on a stick of length $$$(10^9 + 1)$$$ units. The initial position of the $$$i$$$-th ant is $$$a_i$$$ units away from the left side of the stick. Some of the ants are facing left at the beginning, while the others are facing right. All ants will move at a speed of 1 unit per second in the direction they're facing. When two ants meet face to face at the same point, both of them will turn around instantly and move on.
There are also two obstacles on the sides of the stick, one located on the leftmost and the other on the rightmost. When an ant runs into one of them, it will also turn around instantly and move on. However, the obstacles aren't indestructible. The left one will break after $$$a$$$ hits, while the right one will break for $$$b$$$ hits. After an ant passes through a broken obstacle it will fall from the stick. Note that the number of hits is calculated independently for each obstacle, and that the ant which breaks the obstacle will also turn around and will not fall immediately.
In how many seconds will all ants fall from the stick?
There is only one test case in each test file.
The first line of the input contains three integers $$$n$$$, $$$a$$$ and $$$b$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le a, b \le 10^9$$$) indicating the number of ants, the number of hits to break the left obstacle and the number of hits to break the right obstacle.
The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$1 \le a_i \le 10^9$$$, $$$a_i \lt a_{i+1}$$$) indicating the initial position of ants.
The third line contains $$$n$$$ integers $$$d_1, d_2, \cdots, d_n$$$ ($$$d_i \in \{0, 1\}$$$). If $$$d_i = 0$$$ then the $$$i$$$-th ant is facing left initially, otherwise it is facing right.
Output one line containing one integer indicating the number of seconds for all ants to fall from the stick.
2 2 4 2 3 0 1
4000000001
The sample test case is explained as follows.
| Time | Event | Left Hit | Right Hit |
| 2 | Ant 1 hits the left obstacle | 1 | 0 |
| 999999998 | Ant 2 hits the right obstacle | 1 | 1 |
| 1000000000.5 | Ant 1 meets ant 2 at 999999998.5 units from the left | 1 | 1 |
| 1000000003 | Ant 2 hits the right obstacle | 1 | 2 |
| 1999999999 | Ant 1 hits the left obstacle | 2 | 2 |
| 2000000001.5 | Ant 1 meets ant 2 at 2.5 units from the left | 2 | 2 |
| 2000000004 | Ant 1 falls from the left | 2 | 2 |
| 3000000000 | Ant 2 hits the right obstacle | 2 | 3 |
| 4000000001 | Ant 2 falls from the left | 2 | 3 |
BaoBao and DreamGrid are playing a card game. Each player has $$$n$$$ cards in the beginning and there are three types of cards: rock, paper, and scissors.
The game consists of $$$n$$$ rounds. In each round, BaoBao will first play one of his remaining cards (this card is shown to both players). After that, DreamGrid can choose one of his remaining cards and play it (also shown to both players). The score of this round is calculated by referring to the following table:
| DreamGrid $$$\downarrow$$$ $$$\,\,\,\,$$$ BaoBao $$$\rightarrow$$$ | Rock | Paper | Scissors |
| Rock | 0 | -1 | 1 |
| Paper | 1 | 0 | -1 |
| Scissors | -1 | 1 | 0 |
After the round, the two played cards are removed from the game. The score of the whole game is the sum of the score of each round.
BaoBao aims at minimizing the score of the whole game, while DreamGrid aims at maximizing it. Both players know the number of cards of each type his opponent and himself holds in the beginning. What's the final score of the game given that both of them take the best strategy?
There are multiple test cases. The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 10^3$$$) indicating the number of test cases. For each test case:
The first line contains three integers $$$b_r$$$, $$$b_p$$$ and $$$b_s$$$ ($$$0 \le b_r, b_p, b_s \le 10^9$$$), indicating the number of rock, paper and scissors cards BaoBao has.
The second line contains three integers $$$d_r$$$, $$$d_p$$$ and $$$d_s$$$ ($$$0 \le d_r, d_p, d_s \le 10^9$$$), indicating the number of rock, paper and scissors cards DreamGrid has.
It's guaranteed that $$$b_r + b_p + b_s = d_r + d_p + d_s$$$.
For each test case output one line containing one integer indicating the final score of game.
4 4 4 2 10 0 0 0 10 0 2 4 4 1 2 3 3 2 1 10 10 10 10 10 10
-2 2 5 30
This problem was asked by Ema.
Given an array of numbers $$$N$$$ and an integer $$$k$$$, your task is to split $$$N$$$ into $$$k$$$ non-empty consecutive partitions such that the maximum sum of any partition is minimized. Output the length of each of the $$$k$$$ partitions. If there are multiple solutions, output the solution with the largest lexicographical order.
Solution A is considered to be lexicographically larger than Solution B if there exists an integer $$$i$$$($$$1 \le i \le n$$$), where the first $$$i-1$$$ partitions in A and B have the same length, and the $$$i$$$th partition in A is longer than that in B.
For example, given N = [5, 1, 0, 2, 7, -3, 4] and k = 3, you should output [3, 3, 1], since the optimal partition is [5, 1, 0], [2, 7, -3], [4]. Note that this example used this format solely for convenience, your program should follow the format described below.
There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 3 \times 10^5$$$) indicating the length of the array and the number of partitions.
The next line contains $$$n$$$ integer $$$N = [a_1, a_2, \cdots, a_n]$$$ ($$$|a_i| \le 10^9$$$) indicating the array.
It's guaranteed that the sum of $$$n$$$ of all test cases will not exceed $$$6 \times 10^5$$$.
For each test case, output one line containing $$$k$$$ integers indicating the length of each of the $$$k$$$ partitions. Note again that your answer must be the lexicographically largest answer.
3 7 3 5 1 0 2 7 -3 4 6 4 -1 3 -2 4 -3 5 6 2 0 -2 0 -1 -1 0
3 3 1 1 1 2 2 3 3
For a permutation $$$P = p_1, p_2, \cdots, p_n$$$ of $$$n$$$, let $$$f(P, k)$$$ be the number of $$$i$$$ satisfying $$$1 \le i \lt n$$$ and $$$p_i + k = p_{i+1}$$$.
Given two integers $$$n$$$ and $$$k$$$, your task is to find a permutation $$$P$$$ of $$$n$$$ such that $$$f(P, k)$$$ is maximized.
Recall that in a permutation of $$$n$$$, each integer from $$$1$$$ to $$$n$$$ (both inclusive) appears exactly once.
There is only one test case in each test file.
The first and only line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 10^6$$$).
Output one line containing $$$n$$$ integers indicating a permutation $$$P$$$ of $$$n$$$ that maximizes $$$f(P, k)$$$. If there are multiple valid answers you can output any of them.
Please, DO NOT output extra spaces at the end of the line, or your answer may be considered incorrect!
3 1
1 2 3
7 3
2 5 1 4 7 3 6
3 7
1 3 2
There are $$$n$$$ hotpot restaurants numbered from $$$1$$$ to $$$n$$$ in Chengdu and the $$$i$$$-th restaurant serves hotpots of a certain spicy value $$$w_i$$$. A higher spicy value indicates a hotter taste, while a lower spicy value is more gentle (still need to be very careful, though).
We can consider these $$$n$$$ restaurants as nodes on an undirected graph with $$$m$$$ edges. Now we have $$$q$$$ tourists who want to give the hotpots a try. Given the current positions of the tourists and the maximum spicy value they can bear, your task is to calculate the shortest distance between a tourist and the closest restaurant he can accept.
In this problem we define the distance of a path as the number of edges in the path.
There is only one test case in each test file.
The first line contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \le n, m \le 10^5,1 \le q \le 5 \times 10^5$$$) indicating the number of restaurants, the number of edges and the number of tourists.
The second line contains $$$n$$$ integers $$$w_1, w_2, \cdots, w_n$$$ ($$$1 \le w_i \le 100$$$) where $$$w_i$$$ indicates the spicy value of the $$$i$$$-th restaurant.
For the following $$$m$$$ lines, the $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) indicating an edge connecting restaurant $$$u_i$$$ and $$$v_i$$$.
For the following $$$q$$$ lines, the $$$i$$$-th line contains two integers $$$p_i$$$ and $$$a_i$$$ ($$$1 \le p_i \le n$$$, $$$1 \le a_i \le 100$$$) indicating that the $$$i$$$-th tourist is currently at restaurant $$$p_i$$$ and that the maximum spicy value he can accept is $$$a_i$$$.
Output $$$q$$$ lines where the $$$i$$$-th line contains one integer indicating the shortest distance between the $$$i$$$-th tourist and the closest restaurant he can accept. If there is no such restaurant, output '-1' instead.
4 4 5 5 4 2 3 1 2 2 3 3 4 4 1 1 1 1 2 1 3 1 4 1 5
-1 2 1 1 0