Alice the shark loves water. In fact, she can't live without water.
Alice has $$$n$$$ fish tanks. For $$$i=1,2,3, \dots, n$$$, the $$$i$$$-th fish tank has $$$a_i$$$ liters of water in it, where $$$a_i$$$ is a positive integer. Each fish tank has a "potential value": if it contains $$$x$$$ liters of water, then its potential $$$\mathcal{P}(x)$$$ is defined as $$$\mathcal{P}(x) = x \times \mathcal{D}(x)$$$, where $$$\mathcal{D}(x)$$$ is the sum of all digits in $$$x$$$. For example, $$$\mathcal{P}(123) = 123 \times (1 + 2 + 3) = 738$$$, and $$$\mathcal{P}(20000) = 20000 \times (2 + 0 + 0 + 0 + 0) = 40000$$$.
Please help Alice calculate the potential values of all her fish tanks.
The first line contains an integer $$$n$$$. The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$.
Technical specification:
Print $$$n$$$ lines. The $$$i$$$-th line should contain the potential of the $$$i$$$-th fish tank.
4 123 20000 5 998244353
738 40000 25 46917484591
Bob the shark enjoys playing chess. In fact, he has just won the Legendary Grandmaster title.
The sharks do not play chess on a regular chessboard, because they think that's boring. Instead, they have a board with $$$n$$$ rows and $$$m$$$ columns, where each square is either black or white. For each game of chess, they pick a region on the board as the "play region" of the game. The play region should be a rectangle of positive area, with each side parallel to one of the board's sides, and each vertex at the corner of some square on the board. Two regions are the same if they contain the same set of squares on the board, otherwise they are different.
An example of a board with 4 rows and 5 columns. The red rectangle on the right marks a possible play region containing 9 squares. Bob's favorite chess move is the "Bongcloud Attack". He uses this move in chess tournaments very often, because it is always a powerful surprise attack that no opponent would expect. One day, he played the Bongcloud as usual, and the opponent took very long to think about the next move. While the opponent was still thinking, the following question came to Bob's mind: How many different play regions on the board are vertically symmetric? A region is called vertically symmetric if it looks the same after reversing its rows. For example, the region shown above is vertically symmetric. Please help Bob calculate the answer with a program.
The first line contains two integers $$$n$$$ and $$$m$$$.
The following $$$n$$$ lines describe the sharks' board. Each line contains $$$m$$$ characters. The $$$j$$$-th character on the $$$i$$$-th line denotes the color of the square at the $$$i$$$-th row, $$$j$$$-th column: 1 for a white square, or 0 for a black square.
Technical specification:
Print one integer, the answer to Bob's question.
2 2 01 00
7
3 4 0101 0100 0001
42
Carl the shark goes to his favorite restaurant for dinner. There is a special event happening today: if he plays and wins a game, the restaurant will offer free chicken nuggets as prize!
The game is set up as follows:
Then, the game is played by one player. The player should do the following:
Carl has a chance to play the game. Since chicken nuggets are his favorite food, he wishes to get as many chicken nuggets as possible. However, the number of plates is so large that he can't possibly calculate the result of the game. Can you help him out?
The first line consists of one integer $$$n$$$. The second line contains $$$n - 1$$$ integers $$$a_2, a_3, \dots, a_n$$$. The third line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$.
Technical specification:
Print one integer, the maximum amount of chicken nuggets Carl can receive from the game.
3 1 1 3 6 5
9
4 1 2 2 5 6 7 8
26
This is an interactive problem.
Diana the shark has built a new machine for her project: the Discombobulator 3000. It is capable of solving any interactive programming problem that involves a permutation!
One day, while Diana was swimming peacefully, the machine fell out of her pocket and landed on the ocean floor. Because of this, it broke into two pieces. Diana was not able to repair it immediately, but she knew how the machine works, even if it was broken:
Unfortunately, Diana only knew the integer $$$n$$$, and had no knowledge about $$$k$$$ or the sequences. The only way to access the sequences is via a special button on the machine. When you press the button, the machine will ask you for two integers $$$x$$$ and $$$y$$$ and reply with the value $$$\max(a_x, b_y)$$$. The button cannot be pressed for more than $$$2n$$$ times in total, otherwise everything will explode.
Diana was discombobulated by the situation, and now she needs your help. If you can find out the integer $$$k$$$, then she will be able to combine the two pieces back into the Discombobulator 3000. Can you do that by interacting with the machine?
The first line of input contains the integer $$$n$$$.
The input has $$$q$$$ more lines if you press the button $$$q$$$ times. Each of these lines contains an integer - the number that the machine replies with.
Technical specification:
Your output should consist of $$$q+1$$$ lines if you press the button $$$q$$$ times.
Each time you wish to press the button, print a line in the form "? $$$x$$$ $$$y$$$", where $$$x$$$ and $$$y$$$ are the numbers you tell the machine. The machine's reply will be sent as one line of input (described above). Don't forget to flush the output stream after printing a line.
The last line should be in the form "! $$$k$$$", where $$$k$$$ is the integer you have to find.
Your output must satisfy $$$0 \le q \le 2n$$$ and $$$0 \le x, y \le n - 1$$$ in each line.
4 1 2 2 4 2
? 2 3 ? 0 1 ? 0 3 ? 3 1 ? 2 1 ! 1
In the example, the sequences are $$$a = [2,3,1,4]$$$ and $$$b = [4,2,3,1]$$$. The answer is $$$k=1$$$.
Remember that you don't have to find the two sequences, only the integer $$$k$$$.
Emily the shark loves fish. In fact, she can't live without fish.
Emily has $$$n$$$ fish tanks. Each fish tank may have some fish in it. For a set of fish tanks, they are "evenly distributed" if they can be partitioned into two groups of fish tanks, such that the total amount of fish in both groups are equal. For example,
Emily has a total of $$$k$$$ fish in her $$$n$$$ fish tanks, and she wants to rearrange all fish such that:
Please help Emily find such an arrangement, or determine if it's impossible.
The input consists of two integers $$$k$$$ and $$$n$$$.
Technical specification:
If the fish cannot be arranged according to Emily's rules, print the string No.
Otherwise, print the string Yes on the first line. Then on the second line, print a list of $$$n$$$ space-separated integers, denoting the amount of fish in each tank. If there are multiple answers, print any one of them.
9 3
Yes 2 3 4
6 3
No
Frank the shark is conducting a study on the behavior of tropical fish. During the study, he discovered an interesting species of fish, called the Gol fish, which inhabit the underwater terrain in a very bizarre way.
The Gol fish live in an area that can be represented by a square grid with $$$n$$$ rows and $$$n$$$ columns. Each square can be described as a pair $$$(i, j)$$$, where $$$i$$$ and $$$j$$$ denotes the number of the row and column it belongs to. Rows and columns are numbered from $$$0$$$ to $$$n - 1$$$. For each of the squares, there are either 0 or 1 fish living in it. Additionally, there is a sea urchin in one of the squares.
Let's define two different squares to be adjacent if they share a common edge, and be neighbors of each other if they share at least a common vertex. In each day, the following happens in order:
The "state" of all Gol fish can be described with $$$n \times n$$$ numbers, where each number denotes the amount of fish living in a square. Frank wants to conduct a experiment on the fish's behavior. Therefore, he adjusted the fish's positions so that the current state is $$$s$$$, and moved the sea urchin to $$$(r, c)$$$. He also wrote down a state $$$t$$$ that he thinks is the "ideal" state for his study, and an integer $$$d$$$. Is it possible that the state becomes $$$t$$$ in $$$d$$$ or less days?
The first line consists of two integers $$$n$$$ and $$$d$$$. The second line consists of two integers $$$r$$$ and $$$c$$$, denoting the sea urchin's location $$$(r, c)$$$.
Then $$$n$$$ lines follow, each containing $$$n$$$ digits. These lines describe the state $$$s$$$. The $$$j$$$-th digit on the $$$i$$$-th line denotes the number of fish living in the square at $$$(i, j)$$$.
Then $$$n$$$ more lines follow, each containing $$$n$$$ digits. These lines describe the state $$$t$$$. The $$$j$$$-th digit on the $$$i$$$-th line denotes the number of fish living in the square at $$$(i, j)$$$.
Technical specification:
If it's possible to reach the state $$$t$$$ from $$$s$$$ in $$$d$$$ or less days, print the string Yes. Otherwise, print No.
4 2 2 1 0100 1010 0100 0000 0100 1000 0100 0000
Yes
8 4 7 7 01000000 00100000 11100000 00000000 00000000 00000000 00000000 00000000 00000000 00100000 00010000 01110000 00000000 00000000 00000000 00000001
No
7 8 6 6 0100000 0010000 1110000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0001000 0011000 0000000 0000000
Yes
In the first example, it is possible to reach state $$$t$$$ in 2 days:

Gary the shark loves to play puzzles. One day, he learned about the most famous and mind-bending puzzle ever existed: the Rubik's Cube. The Rubik's Cube is a cube-shaped puzzle toy. Each of its faces is divided into a $$$3 \times 3$$$ grid, where each "slice" can be rotated independently. For a solved Rubik's Cube, every side has a unique color, and its color layout is shown below:

Gary has a Rubik's Cube sitting in his toy box, and he's having a hard time solving it. (This is probably due the fact that, according to scientists, most shark species are color blind.) To solve this problem once and for all, he created the powerful Group-Theoretic Machine.
The Group-Theoretic Machine (GTM) is a special machine that can solve any scrambled Rubik's Cube using group-theoretic algorithms. It has six sensors $$$O, R, W, Y, G, B$$$, which correspond to the colors orange, red, white, yellow, green, and blue respectively. Each sensor is located at a fixed position. To increase the stability of the machine, the sensors are designed so that the segments $$$\overline{OR}$$$, $$$\overline{WY}$$$, and $$$\overline{GB}$$$ are parallel to the $$$x$$$-, $$$y$$$-, and $$$z$$$-axes respectively.
For the machine to work, one should first activate it by placing a solved Rubik's Cube inside, such that each sensor touches a face with the corresponding color (touching that face's boundary also counts). Gary has just received a new Rubik's Cube with a side length of $$$d$$$, and he wonders if it can be used to activate the machine. The cube may be oriented or moved freely.
The first line contains one integer $$$t$$$ denoting the number of test cases. Then $$$t$$$ test cases follow.
In each test case, there are 7 lines. The first line contains an integer $$$d$$$. The remaining 6 lines describe the sensors $$$O, R, W, Y, G, B$$$ respectively. Each of them contains three integers $$$x, y, z$$$ denoting the coordinates of a sensor's location.
Technical specifications:
For each test case, if the machine cannot be activated with Gary's new cube, print a line containing the string NO.
Otherwise, print the string YES. Consider a placement of the Rubik's Cube that can activate the machine. Let $$$V_1, V_2, \dots, V_8$$$ denote the Rubik's Cube's vertices in the order shown ($$$V_8$$$ is the remaining vertex at the back so cannot be seen here):

Print 8 more lines. The $$$i$$$-th ($$$i=1,2,\dots,8$$$) line should consist of three space-separated real numbers $$$x, y, z$$$ describing the coordinates of $$$V_i$$$ under said placement. If there are multiple answers, output any one of them.
Your answer will be accepted if the cube you output satisfies:
3 2 -1 0 0 1 0 0 0 -1 0 0 1 0 0 0 -1 0 0 1 5 2 7 8 8 7 8 6 3 8 6 9 8 6 7 4 6 7 10 2 -1 0 0 1 0 0 0 1 0 0 -1 0 0 0 -1 0 0 1
YES 1.000000 1.000000 1.000000 -1.000000 1.000000 1.000000 1.000000 -1.000000 1.000000 -1.000000 -1.000000 1.000000 1.000000 1.000000 -1.000000 -1.000000 1.000000 -1.000000 1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 YES 7.666667 8.666667 9.666667 3.500000 10.159407 7.340593 5.340593 4.500000 11.159407 1.173927 5.992740 8.833333 9.159407 6.340593 5.500000 4.992740 7.833333 3.173927 6.833333 2.173927 6.992740 2.666667 3.666667 4.666667 NO
NOTICE: Contrary to what the statement PDF says, the checker on Codeforces does NOT have 256 bits of precision, due to technical issues with the Polygon system. It uses __float128 instead, but this is enough for intended solutions to pass.
The images above are licensed under CC-BY-SA 4.0 and are modified from existing images by other authors. The original files can be found here:
Hans the shark lives in an underwater country that is divided into $$$n$$$ states, numbered from 1 to $$$n$$$. There are $$$m$$$ bidirectional roads in this country, each of which connects two different states. It is possible to travel from any state to any other state by swimming along the roads.
Hans is planning some journeys around the country. He first chooses a set of states in the country, and calls them the "halting states". Then he defines a "journey" as follows:
In other words, a journey is a walk that starts from a halting state and ends in a different halting state. A walk consists of a sequence of states in which every two adjacent states are connected by a road.
The length of a journey is defined as the number of days spent before it ends, which is also the total number of roads he has traveled. A journey is called "happy" if its length is a multiple of $$$k$$$, where $$$k$$$ is Hans' lucky number. Hans wants to choose the maximum number of halting states, such that every possible journey that ends is happy. Can you help him do it?
The first line contains three integers $$$n, m, k$$$. Then $$$m$$$ lines follow. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ describing a road between the states numbered $$$u_i$$$ and $$$v_i$$$.
Technical specifications:
Output one integer, the maximum number of halting states that Hans can choose such that every possible journey that ends is happy.
5 6 2 1 3 1 5 2 5 2 3 2 4 1 4
3
4 3 3 1 2 2 3 3 4
1
Remember that if no journey can possibly end, then the constraint is satisfied.
In the first example, Hans can choose the states 3, 4, and 5. He can also choose the states 1 and 2, but the number of halting states is not maximized.
In the second example, the maximum number of halting states is 1, as Hans cannot choose more than 1 halting states. For example, if the states 1 and 4 are chosen, then there exists a journey $$$1\rightarrow2\rightarrow3\rightarrow2\rightarrow3\rightarrow4$$$ which has length 5 so is not happy. On the other hand, if state 1 is the only halting state, then no journey can possibly end, so every journey that ends is happy.