After millennia of lurking in the shadows, the Sith have revealed their insidious presence! Jedi Master Qui-Gon Jinn and his padawan Obi-Wan Kenobi were culling droids in the Battle of Naboo's final moments when the Sith Lord Darth Maul ambushed them. Maul lures the pair into the heart of the Theed power generator, an unfathomably deep plasma well dotted with narrow bridges over colossal drops. Here, their fated duel will unfold.
Amid the chaos, Obi-Wan is kicked off the highest bridge all the way to the very bottom of the well. Obi-Wan must now make his way back to the top as soon as possible to rejoin the fight! There are $$$n$$$ bridges each of varying heights $$$h_1, h_2, ... , h_{n-1}, h_n$$$, and the bridge Obi-Wan must return to is of height $$$h_n$$$.
Luckily, Obi-Wan is a highly skilled Jedi apprentice. If a Jedi has strength $$$s$$$, then they are able to jump a height of $$$s$$$ units, meaning that Obi-Wan can jump to any higher bridge if the height difference is less than or equal to $$$s$$$. A Jedi's jump strength $$$s$$$ doesn't change between jumps.
Obi-Wan wants to conserve as much strength as he can to help defeat Darth Maul, so he needs to minimize the strength he allocates to jumping. Help Obi-Wan determine the minimum strength $$$s$$$ he needs to return to the highest bridge. His initial height is at $$$0$$$ units. All of the bridges' heights are in non-decreasing order, with $$$h_n$$$ being the highest.
The first line contains a single integer $$$n \: (1 \leq n \leq 100)$$$ — the number of bridges.
The second line contains $$$n$$$ integers $$$h_1, h_2, ... , h_{n-1}, h_n \: (1 \leq h_i \leq h_{i+1} \leq 1000)$$$ — the height of each bridge in non-decreasing order.
Output a single integer — the minimum strength $$$s$$$ needed to be able to make it to the $$$n$$$th bridge.
310 20 40
20
51 1 2 2 2
1
510 10 10 10 10
10
In the first test case, strength $$$20$$$ is sufficient to make it to the 3rd bridge. A possible path for Obi-Wan could be:
$$$0 \rightarrow 20 \rightarrow 40$$$. He needs strength $$$20$$$ to make both of the jumps.
In the second test case, strength $$$1$$$ is sufficient to make it to the fifth bridge. A possible path for Obi-Wan could be:
$$$0 \rightarrow 1 \rightarrow 2$$$.
He needs strength $$$1$$$ to make both of the jumps. Note that Obi-Wan needs strength $$$0$$$ to jump across bridges of the same height, so he can just jump to any bridge of height 2 and then make it to bridge $$$n$$$ from there.
In the third test case, strength $$$10$$$ is sufficient to make it to the first bridge. It is clear to see that he doesn't need more to jump from the first bridge to the fifth bridge.
The Death Star isn't the only thing Davis and the evil Galactic Empire have in common; they both have a high density of K-pop fans.
There are $$$n$$$ K-pop groups that the Galactic Empire allows its citizens to listen to – if they let them listen to any more than that, there would be massive productivity issues. Each stormtrooper in the 501st legion – Vader's Fist – "stans" (is a fan of) exactly one group, their favorite group. Each stormtrooper also has a favorite song by that group, however, the stormtroopers only share their favorite group with their peers, as sharing their favorite song would be too personal.
Darth Vader has just caught on to the fad, but as the heir to the great Galactic Empire, he wants to be unique. Lord Vader wants to make sure that, for whichever group he chooses as his favorite, he can find at least one favorite song that no stormtrooper has as their favorite song. Is this possible?
The first line contains the positive integer $$$n$$$ $$$(1 \le n \le 100)$$$ — the number of K-pop groups that Vader and the stormtroopers can listen to.
The next $$$n$$$ lines each contain a string $$$g_i$$$ $$$(1 \le |g_i| \le 20)$$$ and a positive integer $$$c_i \: (1 \le c_i \le 100)$$$, with $$$g_i$$$ corresponding to the name of the $$$i$$$-th K-pop group and with $$$c_i$$$ corresponding to the number of songs released by that group. It is guaranteed that group names are distinct.
The next line contains the positive integer $$$m$$$ $$$(1 \le m \le 10^4)$$$ — the number of stormtroopers in Vader's Fist.
The next $$$m$$$ lines each contain a string $$$s_j$$$ $$$(1 \le |s_j| \le 20)$$$ — the favorite group of the $$$j$$$-th stormtrooper.
Determine any one group that Darth Vader can stan as his favorite and print its name (there may be multiple possible answers, but you only need to print one). If there are no such groups, print NO KPOP FOR VADER.
3MONSTA_X 3BTS 2TWICE 26BTSMONSTA_XMONSTA_XBTSTWICEBTS
MONSTA_X
4NewJeans 2BLACKPINK 1StrayKids 1Seventeen 15NewJeansStrayKidsBLACKPINKNewJeansSeventeen
NO KPOP FOR VADER
For test case 1, both MONSTA_X and TWICE are valid answers.
Han and Chewbacca were enjoying a succulent Tatooinian meal at the respectable Mos Eisley cantina. While heading to the bathroom, Han is accosted by the bounty hunter Greedo, looking to claim the price on Hans' head. They take a seat at a booth and discuss the situation, at Greedo's gunpoint. Then, as we all know, Greedo eloquently states "Maclunkey" and two shots are fired immediately after. Greedo is killed, but it is clear that one shot rang out before the other. Who shot first?
Han and Greedo were sitting on horizontal couches directly across from each other at a distance of $$$1$$$ imperial meter, or $$$1000$$$ imperial millimeters apart. Since the cantina can get quite violent, the owners installed laser detectors on and around these couches. These sensors can tell the exact landing time and landing place of a laser shot.
We know Han's shot follows a straight line and lands on Greedo, who is sitting at $$$(0,1000)$$$. We also know Greedo's horrible aim caused his shot to land either to the left or right of Han, who is sitting at $$$(0,0)$$$. Greedo's shot always lands after Han's due to traveling a longer distance. The cantina provides you with the time difference between these shots, i.e., the number of galactic milliseconds that it takes for Greedo's shot to land after Han's shot lands.
Additionally, Han uses a DL-44 heavy-blaster pistol, while Greedo has a DT-12 model. These blasters fire with two different velocities, but they can be tuned to the owner's preference.
Diagram representing the first sample test case You are given 4 pieces of data on one line:
First, an integer $$$x \: (-1000 \le x \le 1000; x \ne 0)$$$ — the location of Greedo's shot on Han's couch, in imperial millimeters.
Next, an integer $$$t \: (1 \le t \le 1000)$$$ — the number of galactic milliseconds between Han's and Greedos' shots landing (Greedo's always lands after).
Finally, two integers $$$v_h$$$ and $$$v_g \: (1 \le v_H, v_G \le 1000)$$$ — the speed (in imperial millimeters per galactic millisecond) of the lasers fired from Han's and Greedo's blasters, respectively.
It is guaranteed that Han and Greedo's firing times are at least $$$10^{-6}$$$ galactic milliseconds apart.
Determine who shot first. Print "Han" if Han shot first, and "Greedo" otherwise (any mix of capitalizations works, e.g. all of "han", "Han", "hAn", and "HAN" would be accepted).
-10 20 30 40
Han
1 50 60 15
Greedo
300 40 77 20
Han
Jar Jar Binks wants to profit from his Jar Jar Drinks, so he opens a bar serving his galaxy-famous Jawa Juice. However, he isn't making much profit from selling drinks alone; so he had the great idea of adding food onto his menu. Jar Jar thinks, and he comes up with a great idea – pizza!
He gets his four-fingered hands on $$$n$$$ rectangular pizzas, where the $$$i$$$-th pizza is $$$w_i \times h_i$$$ inches. But Jar Jar Binks doesn't stop here. Jar Jar Binks loves four-sided regular polygons because four is the largest number he can count up to on his fingers. So the natural conclusion (for him) is to create the biggest square pizza possible!
Jar Jar Binks can do a few things to construct his big square pizza. Beforehand, he can rotate any of his $$$w_i \times h_i$$$ pizzas to become $$$h_i \times w_i$$$ pizzas. He can also cut off unnecessary pieces from any pizza to be reshaped to $$$w_i' \times h_i'$$$ where $$$0 \lt w_i' \le w_i$$$ and $$$0 \lt h_i' \le h_i$$$. Afterward, he can horizontally concatenate some or all of the pizzas to form the larger pizza. Note that any scraps cut off from a pizza are thrown away (into his belly) and the large concatenated pizza cannot be rotated.
But because Jar Jar stinks, he can't do the math to figure out how large he can make his square pizza! So he asks you this – What are the dimensions of the biggest $$$\textbf{square}$$$ pizza Jar Jar Binks can create?
The first line contains one positive integer $$$n \: (1 \le n \le 10^5)$$$ – the number of pizzas Jar Jar Binks has.
Then $$$n$$$ lines follow. The $$$i$$$-th line contains 2 integers $$$a_i$$$, $$$b_i$$$ $$$(1 \le a_i, b_i \le 10^9)$$$, where $$$a_i$$$ denotes the width and $$$b_i$$$ denotes the length of the $$$i$$$-th pizza.
Print one integer – the dimension of $$$1$$$ side of the biggest $$$\textbf{square}$$$ pizza.
51 102 12 54 16 3
5
11000 1
1
In the first test case, notice that one way for Jar Jar Binks to create a $$$5 \times 5$$$ square pizza is to rotate the $$$6 \times 3$$$ pizza and concatenate it with the $$$2 \times 5$$$ pizza. Notice that Jar Jar Binks cannot create a larger square pizza as that would require vertical concatenation of pizzas, or is simply impossible.
Diagram of solution for test case 1. In the second test case, notice that the largest square pizza Jar Jar Binks can create is a $$$1 \times 1$$$ square pizza.
The Separatists are having trouble with the Geonosis Droid Foundry! This foundry produces B1-series battle droids, but each droid produced has many unnecessary parts. The Archduke of the Geonosians, Poggle the Lesser, asked you to salvage as many droids as possible by removing the unnecessary parts.
You are given a string baseline $$$b$$$ which represents the parts for all droids as they come out of the production line. Every produced droid appears this way. Additionally, you are given $$$n$$$ designs $$$d_1, d_2, ..., d_{n-1}, d_{n}$$$, where $$$d_i$$$ is a string that represents the parts that the $$$i$$$-th droid is supposed to have. It is guaranteed that every design is at most as long as the baseline or, more formally, $$$|d_i| \le |b|$$$ for all $$$i \in [1, n]$$$.
For each droid, determine if its design $$$d_i$$$ can be created from the baseline string $$$b$$$ by removing zero or more characters from $$$b$$$, without changing the order of the characters in $$$b$$$ or $$$d_i$$$.
The first line of input contains the string $$$b$$$ $$$(1 \le |b| \le 1000)$$$ — the baseline string consisting of uppercase letters [A-Z].
The second line contains the integer $$$n$$$ $$$(1 \le n \le 1000)$$$ — the number of designs that you must try to produce.
Each of the next $$$n$$$ lines contain a string $$$d_i$$$ $$$(1 \le |d_i| \le |b|)$$$ — the $$$i$$$-th design, also consisting of uppercase letters [A-Z].
Output $$$n$$$ lines where, on the $$$i$$$-th line, print "YES" if $$$d_i$$$ can be created from $$$b$$$ or "NO" otherwise.
ABCDEF3ACEFDCCDE
YES NO YES
JAVAJAVA4AAAAAAAVAAAAAVJAVAJAVA
YES YES NO YES
In the first test case, the first design ACEF is able to be created by removing B and D from ABCDEF.
The second design DC is impossible. Note that CD can be created by removing A, B, E, and F, but we cannot rearrange these letters to DC so this is not useful.
The third design CDE can be created by removing A, B, and F.
The Separatists are still having trouble with the Geonosis Droid Foundry! The issue now is that the B2-series super battle droids are being produced with many unnecessary parts. Poggle the Lesser is even more displeased with this situation and he wants to know how this issue can be resolved.
You are given a string baseline $$$b$$$ which represents the parts for all droids as they come out of the production line. Every produced droid appears this way. You are also given a design string $$$d$$$ which represents how the droids should appear after modification. It is guaranteed that the design is at most as long as the baseline $$$(|d| \le |b|)$$$.
You are looking to remove zero or more characters from $$$b$$$ to produce $$$d$$$, without changing the order of the characters. However, because many parts depend on one another, no two adjacent characters can both be removed. Poggle the Lesser wants to know how many ways $$$d$$$ can be made using this method. Two ways are different if the sets of removed indices are different.
Determine how many different ways $$$d$$$ can be made by removing letters from $$$b$$$. As this result can get quite large, output this result modulo $$$10^9+7$$$.
The first line of input contains the string $$$b$$$ $$$(1 \le |b| \le 500)$$$ — the baseline string consisting of uppercase letters [A-Z].
The second line contains the string $$$d$$$ $$$(1 \le |d| \le 500)$$$ — the design string also consisting of uppercase letters [A-Z].
Output a single integer: the number of unique ways to remove characters from $$$b$$$ that result in $$$d$$$, while not removing two or more characters in a row.
AAAAAAAA
6
ABCABCABC
0
AABBCCABC
4
The Rebel Alliance is celebrating their recent victory at the Battle of Endor with their comrades the Ewoks, small bear-like beings that are native to Endor. Ewoks are notorious for the ceremonial consumption of their enemies, and the swathes of fallen and imprisoned stormtroopers from the recent battle are particularly enticing to them. So the Ewok's leader, Chief Chirpa, commands his tribes to round up the stormtroopers, roast them over a pyre, and then he will distribute them personally to his warriors.
Since this is a very profound and auspicious event, Chief Chirpa wants to follow the traditional guidelines for distributing the roasted stormtroopers. He first lines up each Ewok in a straight line, making note of the position of each Ewok as an integer starting from $$$1$$$. As is tradition, the amount of stormtrooper kebabs each Ewok gets is determined as follows:
- For Ewoks $$$1$$$ and $$$2$$$, Chief Chirpa chooses integers $$$a$$$ and $$$b$$$ that are coprime, and gives them $$$a$$$ and $$$b$$$ kebabs respectively. Two integers are coprime if their greatest common divisor is $$$1$$$.
- For every Ewok after that, the amount of kebabs received is equal to the product of what the previous two received. More formally, the number of kebabs given to the $$$i$$$-th Ewok is $$$c_i = c_{i-1} \cdot c_{i-2}$$$ where $$$i \ge 3$$$. Recall that $$$c_1 = a$$$ and $$$c_2 = b$$$, where $$$a$$$ and $$$b$$$ are the two integers initially chosen by Chief Chirpa.
Though there are plenty of roasted stormtrooper kebabs to go around, there is one very picky Ewok – the famed scout Wicket Wystri Warrick. Wicket is standing at position $$$n$$$ in the line, and he wants exactly $$$k$$$ kebabs, no more and no less (i.e. $$$c_n=k$$$). Chief Chirpa would not dare displease one of his best warriors, but he must also follow the traditional distribution method, so he needs your help to identify whether or not he can choose values for the initial amounts $$$a$$$ and $$$b$$$ such that Wicket at position $$$n$$$ will receive $$$k$$$ kebabs.
Wicket has an unfathomable appetite, so $$$k$$$ may be very large. To accommodate this, you will be provided with the prime factorization of $$$k$$$ as a list of $$$r$$$ distinct prime factors and their exponents $$$(p_1, q_1), (p_2, q_2), ..., (p_{r-1}, q_{r-1}), (p_r, q_r)$$$ such that:
The first line of input contains two integers $$$n$$$ and $$$r$$$ $$$(1 \le n \le 45, 0 \le r \le 10^5)$$$ — the position of the picky Ewok and the number of distinct prime factors in $$$k$$$, respectively.
Each of the next $$$r$$$ lines contain two integers $$$p_i$$$ and $$$q_i$$$ $$$(2 \le p_i \le 999999937, 1 \le q_i \le 10^9)$$$ — a distinct prime factor of $$$k$$$ and its exponent (i.e. the number of times it appears as a factor of $$$k$$$). It is guaranteed that each $$$p_i$$$ is prime and that the list of prime factors is in increasing order $$$(p_i \lt p_{i+1}$$$ for $$$1 \le i \le r-1)$$$.
Print "YES" if it is possible for Chief Chirpa to both distribute the kebabs in the traditional way and satisfy the picky Ewok's preference $$$(c_n=k)$$$, and "NO" otherwise. The letters of the output may be printed in upper or lower case.
1 12 1
YES
2 13 2
YES
5 13 2
YES
6 13 2
NO
5 22 23 3
YES
5 32 15 111 1
NO
4 0
YES
In the first test case, we have $$$n = 1$$$ and $$$k = 2^1 = 2$$$. We can pick $$$a = 2$$$ and $$$b = 1$$$, which satisfies the traditional sequence requirement as well as the preferences of Ewok $$$1$$$.
In the third test case, we have $$$n=5$$$ and $$$k=3^2=9$$$, so we can choose $$$a=3$$$ and $$$b=1$$$. The sequence up to the $$$n$$$th Ewok will be $$$3$$$, $$$1$$$, $$$3$$$, $$$3$$$, $$$9$$$.
In the sixth test case, we have $$$n=6$$$ and $$$k=2^1 \cdot 5^1 \cdot 11^1 = 110$$$. It can be shown that there exists no traditional sequence of kebabs that satisfies the preferences of Ewok $$$n$$$.
May the Fours be with you!
On the unexplored planet of Dagobah, the Jedi Master Yoda is training the young Luke Skywalker in the ways of the Fours! To strengthen Luke's problem-solving skills, Yoda gives Luke some integers. For each integer $$$f_i$$$, Luke must generate an arithmetic expression that evaluates to that integer. Yoda gives Luke four rules to follow for each of his expressions.
1. The expression is a valid C-style arithmetic expression consisting only of operators + - * /, parentheses ( ), and the powerful number 4. The expressions must not contain spaces. Luke must treat each 4 as a separate value – he cannot append two fours together to make 44.
2. The expression must evaluate into the given integer result value $$$f_i$$$.
3. The number of operators in the expression is exactly one less than the number of fours. There can be many parentheses, as long as they match each other as they would in a valid C-style expression.
4. Luke must use the minimum possible amount of fours to make each expression, and his expressions must use 10 or less fours and use 100 characters or less, otherwise the expression is too powerful and may lead Luke to the dark side.
Yoda will provide Luke with a list of $$$n$$$ integers. For each integer $$$f_i$$$, Luke must provide a valid C-style expression fulfilling the above four rules that evaluates to $$$f_i$$$. If no expression can be made that fulfills the four rules, instead output IMPOSSIBLE.
For example, given the integer $$$64$$$, a possible expression is (4+4)*(4+4). However, $$$64$$$ can be calculated with only three 4s, with 4*4*4. Thus, (4+4)*(4+4) would not be an acceptable answer, but 4*4*4, (4*4)*4, ((4*(4)*4)) etc. would be acceptable.
Help Luke master the ways of the Fours!
The first line of input contains the integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the number of integers Yoda will give to Luke.
Each of the next $$$n$$$ lines contains a single integer $$$f_i$$$ $$$(-10^9 \le f \le 10^9)$$$ — an integer for which Luke must generate an expression.
For each integer $$$f_i$$$, output an expression that evaluates to it. If no expressions fulfill all four of Yoda's rules for that $$$f_i$$$, print IMPOSSIBLE. The generated expressions must not contain spaces.
8402142-2115369712321
4 4-4 4*4+4/4+4 (((4/4+4)/4)+4)*(4+4) 4-(4+4+4*4+4/4) ((4+4)*4+4)*((4/(4*4))+4) ((4/(4*4))+4)*(4+((4+4)*(4+4*4))) IMPOSSIBLE
Note that there are many possible ways to generate these expressions.
$$$21$$$ may be obtained with 4*4+4+4/4, 4+4/4+4*4, etc. All of these would be accepted, as all use $$$5$$$ fours, which is the minimum number of fours required to produce $$$21$$$.
$$$153$$$ may also be obtained with (4*4+4/4)*(4+4+4/4) = 17*9 = $$$153$$$. Both use the minimum possible of $$$8$$$ fours, so both would be acceptable.
The Emperor has just launched a revolution against the Jedi. You are a senator on the planet Coruscant and you find yourself in opposition to the Emperor. You decide to meet secretly with two important figures of the old republic, Mon Mothma and Bail Organa, on the planet Alderaan to discuss what lies in the future.
You are interested in the number of paths that can get you to Alderaan. Currently, you are on the planet Coruscant, which is marked as node $$$1$$$ on your ship's navigation system. Alderaan is marked as node $$$a$$$. There exists a safe route between from node $$$i$$$ to node $$$j$$$ if and only if $$$i$$$ divides $$$j$$$ $$$(i \: | \: j; \: i \neq j)$$$. A route is a one-directional edge between two nodes, so a safe route existing from $$$i$$$ to $$$j$$$ does not imply a safe route exists from $$$j$$$ to $$$i$$$.
Unfortunately, there is a crisis on the planet Mustafar, represented by the node $$$b \: (b \neq a)$$$. The Emperor is on his way to Mustafar to retrieve the remains of his newest disciple, just felled by Obi-Wan Kenobi. It is dangerous to share any route with the Emperor, and thus any of the possible paths from Coruscant (node $$$1$$$) to Alderaan (node $$$a$$$) that share a route with any path from Coruscant (node $$$1$$$) to Mustafar (node $$$b$$$) are now not safe.
The ship's captain asked for your help in finding the number of safe paths from Coruscant to Alderaan.
Each test will contain a line with 2 integers $$$a$$$ and $$$b$$$.
The first integer is $$$a \: (2 \leq a \leq 10^{12})$$$ — the value of node $$$a$$$, representing the target planet Alderaan.
The second integer is $$$b \: (2 \leq b \leq 10^{12}, \: b \neq a)$$$ — the value of node $$$b$$$, representing the dangerous planet Mustafar.
For each test case, output a single integer: the number of safe paths from Coruscant (node $$$1$$$) to Alderaan (node $$$a$$$).
It is guaranteed that the answer fits into a 64-bit integer.
6 16
2
5 10
0
10 5
2
In the first test case there are two safe paths: $$$1 \rightarrow 3 \rightarrow 6$$$ and $$$1 \rightarrow 6$$$.
In the second test case it can be shown that none of the paths are safe.
BB-8 is rolling through a maze, represented by a 2D grid with $$$r$$$ rows and $$$c$$$ columns. The grid is comprised of five different characters. "#" represents a wall, and "." represents an empty tile. "P" is a powerup for BB-8, "A" is BB-8's starting point, and "B" is the destination point for it to reach. BB-8 can freely pass through empty tiles, powerups, and its starting and destination points, but cannot travel through walls.
Each second, BB-8 can make a number of moves equal to its power, which starts at $$$1$$$. BB-8 can only move orthogonally through the grid; in other words, it can move one tile up, down, left, or right with a single movement action. It starts on the space marked A and wants to move to the space marked B.
Around the maze are $$$p$$$ powerups marked P. BB-8 must collect every powerup to complete the maze. Whenever it moves over a powerup, it can choose to collect the powerup to increase its power by $$$1$$$, which means it can make up to $$$1$$$ more moves in subsequent seconds. When a powerup is collected, BB-8's current second ends and the space it was on becomes an empty tile so that the powerup cannot be collected again.
Given a maze, determine the least amount of seconds BB-8 can take to reach point "B", starting from point "A", and collecting every powerup.
The first line contains three integers $$$r$$$, $$$c$$$, and $$$p$$$ $$$(4 \le r, c \le 100; \: 0 \le p \le 12)$$$ — the number of rows, columns, and powerups in the grid.
The next $$$r$$$ lines each contain a string of length $$$c$$$ which describes the 2D grid, as explained above.
The perimeter of the grid (first and last rows and columns) are always walls "#".
There is exactly one "A", one "B", and $$$p$$$ "P"s in every maze.
Output a single integer: the minimum number of seconds it takes for BB-8 to reach the destination "B" after collecting every powerup. In the case where BB-8 cannot reach "B" from "A" or it cannot collect all the powerups, output IMPOSSIBLE instead.
5 7 3########P....##.AP#B##P..##########
5
4 5 2######AB###P#P######
IMPOSSIBLE
4 6 5#######APPB##PPP.#######
6
A possible sequence of moves BB-8 can make is shown for the first test case.
1. One tile left.
2. One tile up, and collect a powerup.
3. Two tiles down, and collect a powerup.
4. Two tiles right and one tile up, and collect a powerup.
5. One tile up, two tiles right, and one tile down to get to the destination.
This is an interactive problem. See the section Interaction for more details.
You are an Imperial Colonel sitting in a regular meeting with Darth Vader and the other officers. Lord Vader sighs and goes on his usual rant. "DAE (does anybody else) remember when we had clone troopers, peak fighters that literally took over the galaxy? Now our conscript stormtrooper armies are utterly insignificant next to the power of the force. They couldn't even the side of a barn with their blasters!"
You want to create an elite stormtrooper squadron to impress Lord Vader. To do this, you grab $$$n$$$ stormtroopers from across the galaxy. This new squadron will have a strict meritocratic hierarchy, but to determine this you need to order these $$$n$$$ stormtroopers from strongest to weakest. You decide to run a series of 1v1 competitions. Each day for up to $$$n$$$ days, you will pair up all of the $$$n$$$ stormtroopers into $$$\frac{n}{2}$$$ 1v1 matchups. At the end of the competition, use the results to find a definitive ranking of the $$$n$$$ stormtroopers.
It is guaranteed that no two stormtroopers have equal strength, and the strength of each stormtrooper does not change across different days. It can be assumed that a stronger stormtrooper will always win in a match against a weaker stormtrooper.
The first line contains a positive integer $$$n$$$ ($$$2 \leq n \leq 256$$$, $$$n$$$ is a power of 2) — the number of stormtroopers that need to be ordered.
You can use this website https://acpc-ucd.com/interact.html to assist in testing the interactions.
To create a new pairing, output "?" followed by a permutation of length $$$n$$$, $$$s_1, s_2, ..., s_n$$$ where each odd-indexed stormtrooper $$$s_i$$$ faces $$$s_{i + 1}$$$ during that days' practice. You can create a new set of pairings and query "?" any number of times between $$$[0, n]$$$.
After each "?" query, you must read in $$$\frac{n}{2}$$$ integers $$$w_1, w_2, ..., w_{n / 2}$$$ — the winner of each match. Winner $$$w_j$$$ corresponds to the match between $$$s_{2j-1}$$$ and $$$s_{2j}$$$. For example, $$$w_2$$$ would be the winner of the match between $$$s_3$$$ and $$$s_4$$$ for $$$n \ge 4$$$.
To give your final, definitive ordering of the strength of the stormtroopers, output "!" followed by a permutation of length $$$n$$$ representing each stormtrooper in order from strongest to weakest $$$s_1, s_2, ..., s_n$$$.
A sequence of $$$n$$$ numbers is called a permutation if it contains all integers from 1 to $$$n$$$ exactly once. For example, the sequences [3,1,4,2] and [2,1] are permutations, but [1,2,1], [0,1] and [1,3,4] — are not.
Invalid outputs will result in Wrong Answer.
Flushing the output:
After printing a query, do not forget to output the new-line character 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;
- stdout.flush() in Python;
- search the respective documentation for other languages.
Interactive Problems: Guide for Participants https://codeforces.me/blog/entry/45307
4 4 1 1 3 1 4 3 1
? 4 2 1 3
? 1 2 3 4
? 1 3 2 4
? 2 3 1 4
! 1 3 4 2In the example, "standard output" represents the user output, and "standard input" represents the interactive response to the output. Extra line spaces have been added to the example case for visual clarity.
In the first query ? 4 2 1 3, the response 4 1 indicates that stormtrooper 4 won against stormtrooper 2 and stormtrooper 1 won against stormtrooper 3.
Boba Fett is flying around Cloud City looking for Han Solo so that he can cash in his sizable bounty. He is given a map of $$$n$$$ possible locations at which Han could be and Boba wants to set up some traps around these locations. There are $$$n-1$$$ routes between these locations labeled with $$$e_1, e_2, \dots, e_{n - 1}$$$. These routes form a tree, in which each vertex represents a location and each edge $$$(u, v)$$$ represents a route between locations $$$u$$$ and $$$v$$$.
Let $$$T$$$ be the tree that represents Boba's map. For $$$1 \leq l \leq r \leq n - 1$$$, let $$$T_{l,r}$$$ denote the subgraph of $$$T$$$ obtained from $$$T$$$ by removing all edges not in $$$\{e_l, e_{l+1}, \dots, e_r\}$$$ and all vertices not incident to any edge in $$$\{e_l, e_{l+1}, \dots, e_r\}$$$. Note that $$$T_{l,r}$$$ may not be a tree, but it must be a forest. An interval $$$[l,r]$$$ is called a trap if both of the following hold:
- $$$1 \leq l \leq r \leq n - 1$$$,
- $$$T_{l,r}$$$ is a tree.
In other words, it's a singular connected component and therefore allows Boba to trap his target in those locations. Boba wants your help in counting the total number of possible traps he could set.
For simplicity, we assume that the vertices of $$$T$$$ are numbered by $$$1, 2, \dots, n$$$. Consider the tree $$$T$$$ in Figure 1(a). Figure 1(b) shows $$$T_{2, 4}$$$, which contains the edges $$$\{e_2, e_3, e_4\}$$$ and the vertices incident to at least one of these edges. Figure 1(c) gives $$$T_{2, 6}$$$. In this example, $$$[2, 4]$$$ is a trap because $$$T_{2, 4}$$$ is a tree; $$$[2, 6]$$$ is not a trap, because $$$T_{2,6}$$$ has two connected components.
The first line of the input contains the integer $$$n$$$ $$$(2 \leq n \leq 1.5 \times 10^5)$$$ — the number of nodes in the tree $$$T$$$.
Each of the next $$$n - 1$$$ lines describes an edge of the tree:
The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ $$$(1 \leq u_i, v_i \leq n)$$$ — the two endpoints of the edge $$$e_i$$$.
It is guaranteed that the given edges form a tree of $$$n$$$ nodes.
Output one integer, indicating the number of possible traps. (Please note that the answer may not fit into a 32-bit integer. We advise using 64-bit integers.)
95 63 14 54 37 87 97 42 1
20
71 22 33 44 55 66 7
21
112 31 23 42 52 67 81 78 96 102 11
21
21 2
1
The first example is given in Figure 1. There are $$$19$$$ possible traps: $$$[1, 1]$$$, $$$[1, 4]$$$, $$$[1, 7]$$$, $$$[1, 8]$$$, $$$[2, 2]$$$, $$$[2, 4]$$$, $$$[2, 7]$$$, $$$[2, 8]$$$, $$$[3, 3]$$$, $$$[3, 4]$$$, $$$[3, 7]$$$, $$$[4, 4]$$$, $$$[4, 7]$$$, $$$[5, 5]$$$, $$$[5, 6]$$$, $$$[5, 7]$$$, $$$[6, 6]$$$, $$$[6, 7]$$$, $$$[7, 7]$$$, and $$$[8, 8]$$$.
The second example is a path of $$$6$$$ edges, in which the edges are labeled in increasing order from left to right. In this example, all $$$21$$$ intervals are possible traps.