Thalia is a Legendary Grandmaster in chess. She has \(n\) trophies in a line numbered from \(1\) to \(n\) (from left to right) and a lamp standing next to each of them (the lamps are numbered as the trophies)
A lamp can be directed either to the left or to the right, and it illuminates all trophies in that direction (but not the one it is next to). More formally, Thalia has a string \(s\) consisting only of characters 'L' and 'R' which represents the lamps' current directions. The lamp \(i\) illuminates:
trophies \(1,2,\ldots, i-1\) if \(s_i\) is 'L';
trophies \(i+1,i+2,\ldots, n\) if \(s_i\) is 'R'
She can perform the following operation at most once:
Choose an index \(i\) (\(1 \leq i < n\));
Swap the lamps \(i\) and \(i+1\) (without changing their directions). That is, swap \(s_i\) with \(s_{i+1}\)
Thalia asked you to illuminate all her trophies (make each trophy illuminated by at least one lamp), or to tell her that it is impossible to do so. If it is possible, you can choose to perform an operation or to do nothing. Notice that lamps cannot change direction, it is only allowed to swap adjacent ones
Input
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \leq t \leq 10\,000\)). The description of the test cases follows
The first line of each test case contains a positive integer \(n\) (\(2 \leq n \leq 100\,000\)) — the number of trophies
The second line of each test case contains a string \(s\) of length \(n\) consisting only of characters 'L' and 'R' — the \(i\)-th character describes the direction of the \(i\)-th lamp
It is guaranteed that the sum of \(n\) over all test cases does not exceed \(100\,000\)
Output
For each test case print \(-1\) if it is impossible to illuminate all trophies by performing one operation (or doing nothing). Otherwise, print \(0\) if you choose not to perform the operation (i.e., the trophies are illuminated by the initial positioning of the lamps), or an index \(i\) (\(1 \leq i < n\)) if you choose to swap lamps \(i\) and \(i+1\)
If there are multiple answers, print any
Example
input
1 2 3 4 5 6 7 8 9 10 11 12 13
6 2 LL 2 LR 2 RL 2 RR 7 LLRLLLR 7 RRLRRRL
output
1 2 3 4 5 6
-1 1 0 -1 3 6
Note
In the first example, it is possible to swap lamps \(1\) and \(2\), or do nothing. In any case, the string "LL" is obtained. Not all trophies are illuminated since trophy \(2\) is not illuminated by any lamp — lamp \(1\) illuminates nothing and lamp \(2\) illuminates only the trophy \(1\)
In the second example, it is necessary to swap lamps \(1\) and \(2\). The string becomes "RL". Trophy \(1\) is illuminated by lamp \(2\) and trophy \(2\) is illuminated by lamp \(1\), hence it is possible to illuminate all trophies
In the third example, all trophies are initially illuminated — hence, not performing any operation is a valid solution
In the last two examples performing swaps is not necessary as all trophies are illuminated initially. But, the presented solutions are also valid
MKnez wants to construct an array \(s_1,s_2, \ldots , s_n\) satisfying the following conditions:
Each element is an integer number different from \(0\);
For each pair of adjacent elements their sum is equal to the sum of the whole array
More formally, \(s_i \neq 0\) must hold for each \(1 \leq i \leq n\). Moreover, it must hold that \(s_1 + s_2 + \cdots + s_n = s_i + s_{i+1}\) for each \(1 \leq i < n\)
Help MKnez to construct an array with these properties or determine that it does not exist
Input
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \leq t \leq 100\)). The description of the test cases follows
The only line of each test case contains a single integer \(n\) (\(2 \leq n \leq 1000\)) — the length of the array
Output
For each test case, print "YES" if an array of length \(n\) satisfying the conditions exists. Otherwise, print "NO". If the answer is "YES", on the next line print a sequence \(s_1,s_2, \ldots, s_n\) satisfying the conditions. Each element should be a non-zero integer in the range \([-5000,5000]\), i. e. \(-5000 \leq s_i \leq 5000\) and \(s_i \neq 0\) should hold for each \(1 \leq i \leq n\)
It can be proved that if a solution exists then there also exists one which satisfies the additional constraints on the range
If there are several correct answers, print any of them
Example
input
1 2 3
2 2 3
output
1 2 3
YES 9 5 NO
Note
In the first test case, \([9,5]\) is a valid answer since \(9+5\) (the sum of the two adjacent elements \(s_1+s_2\)) is equal to \(9+5\) (the sum of all elements). Other solutions include \([6,-9], [-1,-2], [-5000,5000], \ldots\)
For the second test case, let us show why some arrays do not satisfy the constraints:
Baltic, a famous chess player who is also a mathematician, has an array \(a_1,a_2, \ldots, a_n\), and he can perform the following operation several (possibly \(0\)) times:
Choose some index \(i\) (\(1 \leq i \leq n\));
multiply \(a_i\) with \(-1\), that is, set \(a_i := -a_i\)
Baltic's favorite number is \(m\), and he wants \(a_1 + a_2 + \cdots + a_m\) to be the smallest of all non-empty prefix sums. More formally, for each \(k = 1,2,\ldots, n\) it should hold that
Please note that multiple smallest prefix sums may exist and that it is only required that \(a_1 + a_2 + \cdots + a_m\) is one of them
Help Baltic find the minimum number of operations required to make \(a_1 + a_2 + \cdots + a_m\) the least of all prefix sums. It can be shown that a valid sequence of operations always exists
Input
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \leq t \leq 10\,000\)). The description of the test cases follows
The first line of each test case contains two integers \(n\) and \(m\) (\(1 \leq m \leq n \leq 2\cdot 10^5\)) — the size of Baltic's array and his favorite number
The second line contains \(n\) integers \(a_1,a_2, \ldots, a_n\) (\(-10^9 \leq a_i \leq 10^9\)) — the array
It is guaranteed that the sum of \(n\) over all test cases does not exceed \(2\cdot 10^5\)
Output
For each test case, print a single integer — the minimum number of required operations
In the first example, we perform the operation \(a_4 := -a_4\). The array becomes \([-1,-2,-3,4]\) and the prefix sums, \([a_1, \ a_1+a_2, \ a_1+a_2+a_3, \ a_1+a_2+a_3+a_4]\), are equal to \([-1,-3,-6,-2]\). Thus \(a_1 + a_2 + a_3=-6\) is the smallest of all prefix sums
In the second example, we perform the operation \(a_3 := -a_3\). The array becomes \([1,2,-3,4]\) with prefix sums equal to \([1,3,0,4]\)
In the third and fourth examples, \(a_1 + a_2 + \cdots + a_m\) is already the smallest of the prefix sums — no operation needs to be performed
In the fifth example, a valid sequence of operations is:
\(a_3 := -a_3\),
\(a_2 := -a_2\),
\(a_5 := -a_5\)
The array becomes \([-2,-3,5,-5,20]\) and its prefix sums are \([-2,-5,0,-5,15]\). Note that \(a_1+a_2=-5\) and \(a_1+a_2+a_3+a_4=-5\) are both the smallest of the prefix sums (and this is a valid solution)
Boris thinks that chess is a tedious game. So he left his tournament early and went to a barber shop as his hair was a bit messy
His current hair can be described by an array \(a_1,a_2,\ldots, a_n\), where \(a_i\) is the height of the hair standing at position \(i\). His desired haircut can be described by an array \(b_1,b_2,\ldots, b_n\) in a similar fashion
The barber has \(m\) razors. Each has its own size and can be used at most once. In one operation, he chooses a razor and cuts a segment of Boris's hair. More formally, an operation is:
Choose any razor which hasn't been used before, let its size be \(x\);
Choose a segment \([l,r]\) (\(1\leq l \leq r \leq n\));
Set \(a_i := \min (a_i,x)\) for each \(l\leq i \leq r\);
Notice that some razors might have equal sizes — the barber can choose some size \(x\) only as many times as the number of razors with size \(x\)
He may perform as many operations as he wants, as long as any razor is used at most once and \(a_i = b_i\) for each \(1 \leq i \leq n\) at the end. He does not have to use all razors
Can you determine whether the barber can give Boris his desired haircut?
Input
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \leq t \leq 20\,000\)). The description of the test cases follows
The first line of each test case contains a positive integer \(n\) (\(3\leq n\leq 2\cdot 10^5\)) — the length of arrays \(a\) and \(b\)
The second line of each test case contains \(n\) positive integers \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 10^9\)) — Boris's current hair
The third line of each test case contains \(n\) positive integers \(b_1, b_2, \ldots, b_n\) (\(1 \leq b_i \leq 10^9\)) — Boris's desired hair
The fourth line of each test case contains a positive integer \(m\) (\(1 \leq m \leq 2\cdot 10^5\)) — the number of razors
The fifth line of each test case contains \(m\) positive integers \(x_1,x_2, \ldots, x_m\) (\(1 \leq x_i \leq 10^9\)) — the sizes of the razors
It is guaranteed that the sum of \(n\) and the sum of \(m\) over all test cases do not exceed \(2\cdot 10^5\)
Output
For each test case, print "YES" if the barber can cut Boris's hair as desired. Otherwise, print "NO"
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses
Anya has gathered \(n\) chess experts numbered from \(1\) to \(n\) for which the following properties hold:
For any pair of players one of the players wins every game against the other (and no draws ever occur);
Transitivity does not necessarily hold — it might happen that \(A\) always beats \(B\), \(B\) always beats \(C\) and \(C\) always beats \(A\)
Anya does not know, for each pair, who is the player who beats the other
To organize a tournament, Anya hosts \(n-1\) games. In each game, she chooses two players. One of them wins and stays, while the other one is disqualified. After all the games are hosted only one player will remain. A player is said to be a candidate master if they can win a tournament (notice that the winner of a tournament may depend on the players selected by Anya in the \(n-1\) games)
Since Anya is a curious girl, she is interested in finding the candidate masters. Unfortunately, she does not have much time. To speed up the process, she will organize up to \(2n\) simuls (short for "simultaneous exhibition", in which one player plays against many)
In one simul, Anya chooses exactly one player who will play against some (at least one) of the other players. The chosen player wins all games they would win in a regular game, and the same holds for losses. After the simul finishes, Anya is only told the total number of games won by the chosen player (but not which ones). Nobody is disqualified during a simul
Can you help Anya host simuls and determine the candidate masters?
The winning players in each pair could be changed between the simuls, but only in a way that preserves the results of all previous simuls. These changes may depend on your queries
Interaction
Firstly, the jury sends one integer \(n\) (\(3 \leq n \leq 250\)) which should be read — the number of players. After that, your program may ask queries or report an answer
To ask a query, print "?\(i \; s_1 s_2 \ldots s_n\)" (without quotes), where \(i\) is the index of the player who will play against some of the other players in the simul. \(s\) is a binary string that denotes the players they play against. \(i\) plays against every player \(j\) for which \(s_j = 1\) holds (and \(s_j = 1\) should hold for at least one \(1 \leq j \leq n\)). Please note that \(s_i = 0\) must hold since a player cannot play against themselves, otherwise, the query is considered to be incorrect
After this, you should read an integer — the number of games player \(i\) has won
When you have identified the answer, you must print "!\(c_1 c_2 \ldots c_n\)" (without quotes) and terminate your program. \(c\) is a binary string which represents the candidate masters. Player \(i\) is a candidate master if \(c_i=1\) holds, otherwise, they are not
If you ask more than \(2n\) queries or if one of the queries is malformed, the interaction terminates immediately and your program receives verdict Wrong Answer
After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
fflush(stdout) or cout.flush() in C++;
System.out.flush() in Java;
flush(output) in Pascal;
stdout.flush() in Python;
see the documentation for other languages
Hacks are disabled in this problem
Examples
input
1 2 3 4 5 6 7
3
1
1
1
output
1 2 3 4 5 6 7 8
? 1 010
? 2 001
? 3 100
! 111
input
1 2 3 4 5 6 7
5
0
3
4
output
1 2 3 4 5 6 7 8
? 5 10110
? 2 10111
? 1 01111
! 10000
Note
In the first example, the first query describes a simul in which player \(1\) plays against player \(2\) (and no one else). The answer to the query is \(1\), meaning that player \(1\) won the only game they played. We can conclude that \(1\) beats \(2\). Similarly, the second query tells us that \(2\) beats \(3\) and the third query tells us that \(3\) beats \(1\). All players are candidate masters in this case as
Player \(1\) can win the tournament if \(2\) and \(3\) play first. \(3\) loses and leaves, while \(2\) stays. \(1\) then plays against \(2\) and wins;
Other players can win in the same fashion
In the second example, the third query describes a simul in which player \(1\) plays against every other player. The answer to the query is \(4\), meaning that they won every game they played. It can be concluded that player \(1\) also beats every other player. They can never lose, hence they are the only player who can remain at the end of every possible tournament, and the only possible candidate master
Misha had been banned from playing chess for good since he was accused of cheating with an engine. Therefore, he retired and decided to become a xorcerer
One day, while taking a walk in a park, Misha came across a rooted tree with nodes numbered from \(1\) to \(n\). The root of the tree is node \(1\)
For each \(1\le i\le n\), node \(i\) contains \(a_i\) stones in it. Misha has recently learned a new spell in his xorcery class and wants to test it out. A spell consists of:
Choose some node \(i\) (\(1 \leq i \leq n\))
Calculate the bitwise XOR\(x\) of all \(a_j\) such that node \(j\) is in the subtree of \(i\) (\(i\) belongs to its own subtree)
Set \(a_j\) equal to \(x\) for all nodes \(j\) in the subtree of \(i\)
Misha can perform at most \(2n\) spells and he wants to remove all stones from the tree. More formally, he wants \(a_i=0\) to hold for each \(1\leq i \leq n\). Can you help him perform the spells?
A tree with \(n\) nodes is a connected acyclic graph which contains \(n-1\) edges. The subtree of node \(i\) is the set of all nodes \(j\) such that \(i\) lies on the simple path from \(1\) (the root) to \(j\). We consider \(i\) to be contained in its own subtree
Input
The first line contains a single integer \(n\) (\(2 \leq n \leq 2\cdot 10^5\)) — the size of the tree
The second line contains an array of integers \(a_1,a_2,\ldots, a_n\) (\(0 \leq a_i \leq 31\)), describing the number of stones in each node initially
The third line contains an array of integers \(p_2,p_3,\ldots, p_n\) (\(1 \leq p_i \leq i-1\)), where \(p_i\) means that there is an edge connecting \(p_i\) and \(i\)
Output
If there is not a valid sequence of spells, output \(-1\)
Otherwise, output a single integer \(q\) (\(0 \leq q \leq 2n\)) in the first line — the number of performed spells
In the second line output a sequence of integers \(v_1,v_2,\ldots,v_q\) (\(1 \leq v_i \leq n\)) — the \(i\)-th spell will be performed on the subtree of node \(v_i\). Please note that order matters
If multiple solutions exist, output any. You don't have to minimize the number of operations
Examples
input
1 2 3
2 13 13 1
output
1 2
1 1
input
1 2 3
7 5 2 8 3 4 1 31 1 1 2 2 3 3
output
1
-1
input
1 2 3
9 3 31 1 2 7 30 7 3 1 1 1 1 2 5 5 3 4
output
1 2
6 3 2 3 1 2 2
Note
Please refer to the following pictures for an explanation of the third test. Only the first \(4\) spells are shown since the last \(2\) do nothing. The first picture represents the tree initially with the number of stones for each node written above it in green. Changes applied by the current spell are highlighted in red
代码参考
Show code
G - The Game of the Century
The time has finally come, MKnez and Baltic are to host The Game of the Century. For that purpose, they built a village to lodge its participants
The village has the shape of an equilateral triangle delimited by three roads of length \(n\). It is cut into \(n^2\) smaller equilateral triangles, of side length \(1\), by \(3n-3\) additional roads which run parallel to the sides. See the figure for \(n=3\). Each of the \(3n\) roads is made of multiple (possibly \(1\)) road segments of length \(1\) which connect adjacent intersections
The direction has already been chosen for each of the \(3n\) roads (so, for each road, the same direction is assigned to all its road segments). Traffic can only go in the specified directions (i. e. the roads are monodirectional)
You are tasked with making adjustments to the traffic plan so that from each intersection it is possible to reach every other intersection. Specifically, you can invert the traffic direction of any number of road segments of length \(1\). What is the minimal number of road segments for which you need to invert the traffic direction?
Input
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \leq t \leq 10\,000\)). The description of the test cases follows
The first line of each test case contains a positive integer \(n\) (\(1\leq n\leq 10^5\)) — the size of the triangular village's sides
Three lines follow, each containing a binary string of length \(n\) which describes the traffic directions of the roads
The \(i\)-th of the following three lines contains a binary string \(s_i\) of length \(n\) representing the direction of each road parallel to the road segment denoted by \(i\) in the picture above. In particular, the \(j\)-th character of \(s_i\) is "1" if the \(j\)-th shortest road (parallel to the road segment denoted by \(i\) in the picture) has the same direction of the road segment denoted by \(i\) in the picture, while it is "0" if it has the opposite direction. So the first character of \(s_i\) describes the direction of the road containing only \(1\) road segment, while the last character describes the direction of the road containing \(n\) road segments
It is guaranteed that the sum of \(n\) over all test cases does not exceed \(10^5\)
Output
For each test case, print the minimum number of road segments for which you need to invert the traffic direction
Example
input
1 2 3 4 5 6 7 8 9 10 11 12 13
3 3 001 001 010 1 0 0 0 3 111 011 100
output
1 2 3
2 0 3
Note
The first example corresponds to the picture in the statement. There exist multiple solutions that invert the traffic direction of exactly \(2\) road segments, but inverting only \(1\) road segment never makes it possible to reach every intersection from any other. One of the possible solutions is shown in the picture below in which the inverted road segments are highlighted in blue
In the second example, the answer is \(0\) since it is already possible to reach every intersection from any other
代码参考
Show code
H - Olympic Team Building
Iron and Werewolf are participating in a chess Olympiad, so they want to practice team building. They gathered \(n\) players, where \(n\) is a power of \(2\), and they will play sports. Iron and Werewolf are among those \(n\) people
One of the sports is tug of war. For each \(1\leq i \leq n\), the \(i\)-th player has strength \(s_i\). Elimination rounds will be held until only one player remains — we call that player the absolute winner
In each round:
Assume that \(m>1\) players are still in the game, where \(m\) is a power of \(2\)
The \(m\) players are split into two teams of equal sizes (i. e., with \(m/2\) players in each team). The strength of a team is the sum of the strengths of its players
If the teams have equal strengths, Iron chooses who wins; otherwise, the stronger team wins
Every player in the losing team is eliminated, so \(m/2\) players remain
Iron already knows each player's strength and is wondering who can become the absolute winner and who can't if he may choose how the teams will be formed in each round, as well as the winning team in case of equal strengths
Input
The first line contains a single integer \(n\) (\(4 \leq n \leq 32\)) — the number of players participating in tug of war. It is guaranteed that \(n\) is a power of \(2\)
The second line consists of a sequence \(s_1,s_2, \ldots, s_n\) of integers (\(1 \leq s_i \leq 10^{15}\)) — the strengths of the players
Output
In a single line output a binary string \(s\) of length \(n\) — the \(i\)-th character of \(s\) should be \(1\) if the \(i\)-th player can become the absolute winner and it should be \(0\) otherwise
In the first example, players \(1\) and \(4\) with their respective strengths of \(60\) and \(87\) can become the absolute winners
Let's describe the process for player \(1\). Firstly, we divide the players into teams \([1,3]\) and \([2,4]\). Strengths of those two teams are \(60+59=119\) and \(32+87=119\). They they are equal, Iron can choose to disqualify any of the two teams. Let his choice be the second team
We are left with players \(1\) and \(3\). Since \(1\) has greater strength (\(60>59\)) they win and are declared the absolute winner as they are the last remaining player
In the third example, the strengths of the remaining players may look like \([8,8,8,8,4,4,4,4] \rightarrow [8,8,4,4] \rightarrow [8,4] \rightarrow [8]\). Each person with strength \(8\) can become the absolute winner and it can be proved that others can't
