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
代码参考
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
代码参考
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
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
代码参考
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
代码参考
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
