Fish likes playing games, and recently he is addicted to Autochess.
There are $$$N$$$ spots (initially empty) in a line named waiting zone, and Fish can add some chessmen into it. Each spot can be occupied by exactly one chessman and each chessman has a name and a level tag (1,2 or 3). Whenever Fish decides to add a chessman named $$$s$$$ of level 1 into the waiting zone, some routines will be on process in order:
- Firstly, if there is a chessman named $$$s$$$ of level 3 in the waiting zone, Fish's operation fails and the process continue(skip following operations and move to add next chessmen).
- Secondly, if there are already $$$K-1$$$ chessmen named $$$s$$$ of level $$$1$$$ in the waiting zone, all these chessmen will be removed and the chessman Fish holds will upgrade to level 2, and if at this time there are already $$$K-1$$$ chessmen named $$$s$$$ of level $$$2$$$, all these chessmen will be removed and the chessman Fish holds will upgrade to level 3.
- Finally, if there are any spots available, the chessman Fish holds will be placed in the leftmost one.
Fish decides to add $$$M$$$ chessmen of level 1 into the waiting zone, so please help him figure out the final status of the waiting zone.
The first line of input contains an integer $$$T$$$, representing the number of test cases.
Then for each test case:
The first line contains three integers $$$M, N, K$$$, the number of chessmen Fish wants to add, the number of spots in waiting zone and the parameter in the process.
Then $$$M$$$ lines follow, each line containing a string $$$s$$$ consisting of only lowercase Latin characters, which is the name of chessman Fish wants to add.
For each test case, you should output Case $$$x$$$: first, where $$$x$$$ indicates the case number starting from $$$1$$$. Then $$$N$$$ strings separated by one space follow, representing the final status of the waiting zone. Each string is the combination of the name and the level tag of the chessman in that spot: for those of level 1, use the name only; for those of level 2 or 3, use the name followed by an extra 2 or 3 respectively. If one spot is empty, print -1 instead.
2 9 7 3 axe axe jugg axe jugg jugg mars axe axe 10 7 2 axe axe jugg axe jugg jugg mars axe axe mars
Case 1: axe2 jugg2 mars axe axe -1 -1 Case 2: axe3 jugg2 mars2 jugg -1 -1 -1
$$$1 \le T \le 100$$$
$$$1 \le N, M\le 10^5$$$
$$$2 \le K \le N$$$
Length of $$$s$$$ will not exceed $$$10$$$
For $$$90\%$$$ test cases: $$$1 \le N, M, K \le 1000$$$
Packing items into a bin is well known as packing problem, and Fish is studying it too. As a beginner, he starts with $$$2$$$-dimension-version problem with $$$2$$$ rectangle-shape items. He just wants to find a convex polygon with the smallest area so that these two items can be well included in it. You should notice that these two items can not overlap each other and you can shift or rotate them in the plane if you like.
Please help Fish solve the problem.
The first line of input contains an integer $$$T$$$, representing the number of test cases. Then following $$$T$$$ lines, each line representing one test case.
For each test case there are four integers $$$w_1, h_1, w_2, h_2$$$ separated by one space telling the width and length of these two items respectively.
For each test case, you should output Case $$$x$$$: $$$y$$$ in one line, where $$$x$$$ indicates the case number starting from $$$1$$$ and $$$y$$$ represents the smallest area.
Your answers will be consider correct if its absolute error does not exceed $$$10^{-6}$$$.
2 1 3 2 4 2 3 4 5
Case 1: 11.5 Case 2: 27.0
$$$1 \le T \le 100$$$
$$$1\le w_1, h_1, w_2, h_1 \le 100$$$
Fish is learning functions! He has a linear function $$$f(x) = Ax + B$$$ and $$$N$$$ numbers $$$x_1,x_2,\cdots,x_N$$$. Now he is curious about for each function $$$g(x)$$$ in
how to calculate the difference between $$$f(g(x))$$$ and $$$g(f(x))$$$.
As smart as Fish is, he soon comes up with a function $$$D(x)=|f(g(x))-x|+|g(f(x))-x|$$$ and uses the sum over $$${x_1,x_2,\cdots,x_N}$$$ as the difference.
Can you tell him all the differences immediately?
The first line of input contains an integer $$$T$$$, representing the number of test cases.
Then for each test case:
The first line contains two integers $$$N$$$, $$$M$$$ as mentioned above and then two real numbers $$$A$$$, $$$B$$$ indicating the given function $$$f(x) = Ax + B$$$.
The second line contains $$$N$$$ real numbers $$$x_1,x_2,\cdots,x_N$$$.
Then $$$M$$$ lines follow, each line containing two real numbers $$$c_i$$$, $$$d_i$$$ indicating a function $$$g_i(x)=c_ix+d_i$$$ mentioned above.
All numbers in the same line are separated by one space.
For each test case, you should output Case $$$x$$$: in the first line, where x indicates the case number starting from 1.
Then $$$M$$$ lines follow, the $$$i$$$-th line of which contains a real number representing the difference for given function $$$g_i(x)$$$.
Your answers will be considered correct if its absolute error does not exceed $$$10^{-6}$$$.
2 3 2 2.0 3.0 1.0 2.0 3.0 0.4 -2.0 0.6 -5.0 3 2 2.5 2.0 1.0 2.0 3.0 0.4 -2.0 0.6 -5.0
Case 1: 7.800000 28.200000 Case 2: 12.600000 36.900000
$$$1\le T\le 100$$$
$$$1\le N, M\le 10^5$$$
$$$-100 \le A,B,x_i,c_i,d_i \le 100$$$
For $$$90\%$$$ test cases: $$$\max(N, M) \le 1000$$$
Fish has a tree with $$$N$$$ nodes numbered from $$$1$$$ to $$$N$$$, and for each node there is a label attached to it. These labels are integers ranging from $$$1$$$ to $$$N$$$. Now Fish wants to divide the tree into many parts and each part is a connected component in the tree. There are so many ways to achieve it, right? But now Fish defines a part as a good part if there is at least one label appears only in this part.
Please tell Fish how many good parts he can get at most in one division.
The first line of input contains an integer $$$T$$$, representing the number of test cases.
Then for each test case:
The first line contains one integer $$$N$$$ as mentioned above.
The second line contains $$$N$$$ integers, representing the label for each node.
Then $$$N - 1$$$ lines follow, each line containing two numbers $$$a, b$$$, which means that there is an edge connecting node $$$a$$$ and node $$$b$$$.
For each test case, you should output Case $$$x$$$: $$$y$$$, where $$$x$$$ indicates the case number starting from $$$1$$$, and $$$y$$$ is the number of good parts Fish can get at most in one division.
2 6 1 1 2 2 3 3 1 2 2 3 2 4 1 5 5 6 6 1 1 2 2 3 3 1 2 1 3 3 4 1 5 5 6
Case 1: 2 Case 2: 3
$$$1 \le T \le 100$$$
$$$1 \le N \le 10^5$$$
$$$1 \le a, b \le N$$$
For $$$90\%$$$ test cases: $$$N \le 1000$$$
Fish has a directed graph and there is a label attached to each edge. A label is an integer ranging from $$$[0,9]$$$. If he chooses a vertex as start point, moves along $$$K$$$ edges in the graph, and writes down the labels in the edges walking through as $$$l_1,l_2,\cdots,l_K$$$, he can easily concatenate them to get a decimal integer $$$l=\overline{l_1l_2\cdots l_K}$$$.
Now he wonders, given $$$P$$$ and $$$X$$$, how many ways he can move so as to get a number $$$l$$$ satisfying $$$l \equiv X \pmod P$$$. Two ways are considered different if the order of edges walking through is different.
The first line of input contains an integer $$$T$$$, representing the number of test cases.
Then for each test case:
The first line contains five integers $$$N, M, K, P, X$$$ as mentioned above, separated by one space .
Then $$$M$$$ lines follow, each line containing three integers $$$u, v, w$$$ which means that there exists an edge from node $$$u$$$ to node $$$v$$$ with label $$$w$$$.
For each test case, you should output Case $$$x$$$: $$$y$$$, where $$$x$$$ indicates the case number starting from $$$1$$$ and $$$y$$$ is the number of ways.
Since $$$y$$$ can be very large, you should output $$$y \bmod (10^9+7)$$$ instead.
3 4 4 3 3 0 1 2 1 2 3 1 3 4 1 4 1 1 4 4 3 2 1 1 2 1 2 3 1 3 4 2 4 1 1 4 4 4 1111 0 1 2 1 2 3 1 3 4 1 4 1 1
Case 1: 4 Case 2: 3 Case 3: 4
$$$1\le T\le 100$$$
$$$1\le N\le 100$$$
$$$1\le M\le 1000$$$
$$$1\le K\le 8$$$
$$$1\le P \lt 10^K$$$
$$$0\le X \lt P$$$
For $$$90\%$$$ test cases: $$$N\le20$$$, $$$M\le100$$$, $$$K\le 6$$$
Fish is retired from programming, so he goes back home and becomes a farmer.
It is important to know the total sunshine time for a specific position in a day. If we assume that his farm is a segment from $$$(0, 0)$$$ to $$$(W, 0)$$$, the sun above can be seen to move from $$$(0, H)$$$ to $$$(W, H)$$$ at a constant speed. Whatever the precise value for the speed is, what we care is just the relevant sunshine time in a day, which is the ratio of actual sunshine time to the total time for the sun moving from the start to the end.
At the same time, there are $$$N$$$ stationary clouds on the sky in a day, and each cloud can be regarded as a segment paralleling to the farm. You should know that the light moves straightly, so the clouds may block the sunshine in some time for some places.
Please help Fish figure out the relevant sunshine time in a day for some positions.
The first line of input contains an integer $$$T$$$, representing the number of test cases.
Then for each test case:
The first line contains four integers $$$N, W, H, Q$$$, the number of clouds, and range of the farm, the height of the sun and the number of queries. Then $$$N$$$ lines follow, each line containing three integers $$$x_1, x_2, y$$$, which means that there is a cloud from $$$(x_1, y)$$$ to $$$(x_2, y)$$$.
Then $$$Q$$$ lines follow, each line containing one integer $$$x$$$, which means that Fish wants to know the answer for position $$$(x, 0)$$$.
For each test case, you should output Case $$$x$$$: first, where $$$x$$$ indicates the case number starting from $$$1$$$. Then $$$Q$$$ lines follow, each line containing a real number representing the answer.
Your answer will be consider correct if its absolute error does not exceed $$$10^{-6}$$$.
2 1 4 4 5 1 3 2 0 1 2 3 4 2 4 4 5 1 2 2 2 3 3 0 1 2 3 4
Case 1: 0.50000000 0.25000000 0.00000000 0.25000000 0.50000000 Case 2: 0.50000000 0.33333333 0.16666667 0.41666667 0.66666667
$$$1 \le T \le 100$$$
$$$1 \le N \le 1000$$$
$$$1 \le W,H \le 10^6$$$
$$$1 \le Q \le 5 \times 10^5$$$
$$$0 \le x_1 \lt x_2 \le W$$$
$$$1 \le y \lt H$$$
For $$$90\%$$$ test cases: $$$N \le 100$$$, $$$Q\le 1000$$$
Alice and Bob always like playing games with each other and today they found a new game about primes.
There are two positive integers $$$x$$$ and $$$y$$$ in the game, and Alice and Bob move in turn. At each turn, the current player can choose one integer and subtract it by $$$1$$$ (making $$$(x, y)$$$ to $$$(x - 1, y)$$$ or to $$$( x, y - 1)$$$). The game ends when one of following conditions is met and the winner is specified at the same time:
- When $$$x$$$ or $$$y$$$ equals to $$$K$$$: Bob wins.
- When $$$x$$$ and $$$y$$$ are both primes: Alice wins.
- When both of the previous conditions are satisfied at the same time: Bob wins.
Now $$$x$$$, $$$y$$$, $$$K$$$ and who moves first are given, can you determine who will finally win the game if they both play optimally?
The first line of input contains an integer $$$T$$$, representing the number of test cases. Then following $$$T$$$ lines and each line contains one test case.
For each test case, there are four integers $$$x$$$, $$$y$$$, $$$K$$$ and $$$w$$$ separated by exactly one space. $$$x$$$,$$$y$$$,$$$K$$$ are mentioned above. $$$w=0$$$ when Alice moves first and $$$w = 1$$$ when Bob moves first.
For each test case, you should output Case $$$x$$$: name in one line, where $$$x$$$ indicates the case number starting from 1, and name is the player who will win the game.
4 4 9 2 0 7 10 2 0 6 39 2 0 5 28 2 0
Case 1: Alice Case 2: Alice Case 3: Alice Case 4: Bob
$$$1 \le T \le 100$$$
$$$2 \le x, y \le 10^6$$$
$$$2 \le K \le \min(x, y)$$$
$$$0 \le w \le 1$$$
For $$$90\%$$$ test cases: $$$\max(x, y) \le 1000$$$
Fish just participated in a programming contest. Before the final standing being public, he hacks the database and wants to change his result!
The database he accessed records the number of times he submitted for each problem and the result (AC or not) for each submission. Soon he finds out that even thought the time for each submission is stored in random order, he can not change it at all (neither the number of submissions for each problem). What he can modify is problem id and result for each submission. In order not to make things too strange, there should not be any submissions for a problem after he has already got an AC in this problem in the end.
You must have known that participants are ranked according to the most problems solved and then ranked by least penalty for those in the same place. The penalty is the sum of the time consumed for each problem solved. The time consumed for a solved problem is the time for its first AC submission, plus $$$20$$$ for every previously not AC submissions for that problem.
Please help Fish find the best result he can get.
The first line of input contains an integer $$$T$$$, representing the number of test cases.
Then for each test case:
The first line contains two integers $$$N, M$$$, the number of submissions and number of problems.
The second line contains $$$N$$$ integers $$$t_i$$$, the time of each submission.
The third line contains $$$M$$$ integers $$$c_i$$$, the number of submissions on each problem.
For each test cases, you should output Case $$$x$$$: $$$y$$$, where $$$x$$$ indicates the case number starting from $$$1$$$, and $$$y$$$ is the penalty for his best result.
2 4 2 10 20 30 40 2 2 4 3 10 20 30 40 1 1 2
Case 1: 100 Case 2: 90
$$$1 \le T \le 100$$$
$$$1 \le N \le 10^5$$$
$$$1 \le M \le min(N, 13)$$$
$$$1 \le t_i \le 300$$$
$$$\sum c_i = N$$$
For $$$90\%$$$ test cases: $$$N \le 100$$$
Fish was retired from programming, and now he goes back home and runs a shop.
There are $$$N$$$ kinds of goods in sale in his shop, and the $$$i$$$-th goods will be sold exactly $$$x_i$$$ pieces everyday. However, as his inventory shelf has a fixed and limited volume $$$V$$$, he has to manage the distribution of these goods. To do so, he wants to assign a real value $$$v_i$$$ to $$$i$$$-th goods as its maximum quantity storing in the shelf such that $$$\sum v_i = V$$$. When one kind of goods is sold out, he can refill the shelf with this goods to its maximum quantity. As a result, for $$$i$$$-th goods, he will refill $$$\dfrac{x_i }{ v_i}$$$ times per day.
Please help Fish determine the $$$v_i$$$ for all goods so that the number of times he use to refill all the goods everyday is minimum.
The first line of input contains an integer $$$T$$$, representing the number of test cases.
Then for each test case:
The first line contains two integers $$$N, V$$$ as mentioned above.
The second line contains $$$N$$$ integers $$$x_1,x_2,\cdots,x_N$$$ as mentioned above.
All numbers in the same line are separated by one space.
For each test case, you should output Case $$$x$$$: $$$y$$$, where $$$x$$$ indicates the case number starting from $$$1$$$, and $$$y$$$ is the minimum number of times he refills the goods of all kinds in one day.
Your answer will be considered correct if its absolute error does not exceed $$$10^{-6}$$$.
2 2 2 1 1 2 2 2 8
Case 1: 2.000000 Case 2: 9.000000
$$$1 \le T \le 100$$$
$$$1 \le N \le 10^5$$$
$$$1 \le V \le 10^9$$$
For $$$90\%$$$ test cases: $$$N \le 100$$$
Fish is standing at position $$$0$$$ on an axis. He wants to move to position $$$K$$$ now but he has to jump in a really strange way!
There are three choices: $$$1$$$,$$$2$$$ and $$$3$$$ and each time he can choose and use exactly one choice. Each choice can be used for infinite times. When he chooses an unused choice $$$j$$$, he will jump forward $$$j$$$ step(s). And when he chooses an used choice $$$j$$$ again, he will jump $$$x+3$$$ steps forward, where $$$x$$$ is the number of steps that he jumped in the last time he chose this choice.
Please help Fish figure out what's the minimum number of times needed, and the total number of ways he can choose no matter the total number of times.
The first line of input contains an integer $$$T$$$, representing the number of test cases.
Then for each test case there is exactly one number $$$K$$$ which is mentioned above in one line.
For each test case, you should output Case $$$x$$$: $$$y$$$ $$$z$$$ in one line, where $$$x$$$ indicates the case number starting from $$$1$$$, $$$y$$$ is the minimum number of times needed and $$$z$$$ is the total number of ways no matter the total number of times. Since $$$z$$$ can be very large, you should output $$$z \bmod (10^9 + 7)$$$ instead.
3 5 14 100
Case 1: 2 3 Case 2: 4 10 Case 3: 8 111211
$$$1 \le T \le 200$$$
$$$1 \le K \le 10^7$$$
For $$$90\%$$$ test cases: $$$K \le 1000$$$
Fish is extremely good at maze game and he becomes king of maze. This time he turns to build a tricky maze game and invite Ruins to solve.
The maze can be simply treated as a $$$N\times M$$$ gird, and some cells inside are walls where one can not move into. In this game, Ruins starts from one cell and he can move into any four-connected neighbor cells if empty. The length of a path in the maze is defined as the number of moves he have to do from the start to the end and his goal is to escape from the maze. As he is a smart guy, he always uses the shortest path strategy: he will always choose the shortest path from current cell to the exit, and moves to the next cell in this path. If there are multiple cells available, he will consider the cell in the top $$$(x - 1, y)$$$, underneath $$$(x + 1, y)$$$, in the left $$$(x, y - 1)$$$, in the right $$$(x, y + 1)$$$ in order and moves to the available one (in one of shortest path) if he is currently in $$$(x,y)$$$.
Fish's maze is a little different: besides the exit, walls and empty cells in all maze games, there is a different kind of cells: lift, which is controllable so that he can change cell of this kind into empty cell or into wall every time he wants. To make this game more interesting, before Ruins's next move, Fish will change some lift cells (or none) into walls and let the remainders become empty cells and wait for Ruins's decision. Of course, if Ruins is standing on a lift cell, Fish can not change this cell into wall.
Just help Fish to find a strategy to trap Ruins in the maze as long as possible!
The first line of input contains an integer $$$T$$$, representing the number of test cases.
Then for each test case:
The first line contains three integers $$$N, M, Q$$$, representing the number of rows of the maze, the number of columns of the maze and the number of start cells you have to deal with.
Then $$$N$$$ lines follow, the $$$i$$$-th line containing a string of length $$$M$$$ representing a row in the maze, the $$$j$$$-th of which represents the cell of $$$(i,j)$$$ . In the maze, "$$$\mathsf{.}$$$" represents empty cell, "$$$\mathsf{\#}$$$" represents wall, "$$$\mathsf{?}$$$" represents lift cell and "$$$\mathsf{E}$$$" represent the exit. It is guaranteed that there is exactly one "$$$\mathsf{E}$$$" in a maze.
Then $$$Q$$$ lines follow, each line containing two integers $$$x, y$$$ which is the start cell of Ruins in one game for given maze, the start cell will never be a wall.
For each test case, you should output Case $$$x$$$: first, where $$$x$$$ indicates the case number starting from $$$1$$$. Then $$$Q$$$ lines follow, each line containing one integer representing the longest time you can trap Ruins in the maze for the given start cell. If you can trap him forever, output -1.
2 4 5 4 ..E.. ..... .?#?. ..... 1 1 4 1 4 2 4 3 4 7 6 ...E... ....... .??#??. ....... 1 1 4 1 4 2 4 3 4 4 4 5
Case 1: 2 5 6 -1 Case 2: 3 6 -1 -1 -1 -1
$$$1\le T\le 100$$$
$$$1\le N,M\le 50$$$
Denote the number of "$$$\mathsf{?}$$$" in a maze as $$$K$$$, $$$0\le K\le 10$$$
$$$1\le Q\le N\times M$$$
$$$1\le x\le N$$$
$$$1\le y\le M$$$
For $$$90\%$$$ test cases: $$$\max(N, M) \le 10$$$