Seo, B21 and Lowie tested the new version of the game Monopoly: Amsopoly. This game is designed specifically to sell to students and alumni of the Hanoi - Amsterdam High School.
In the simplest version, the game map consists of $$$N+1$$$ real estate areas. The first one is called "starting position": it belongs to the government and all players start from there in the beginning of the game. The other $$$N$$$ areas are placed in a circle in the following manner: the $$$2^{nd}$$$ placed after the $$$1^{st}$$$, the $$$3^{rd}$$$ placed after the $$$2^{nd}$$$ and so on. In the end, the $$$(N+1)^{th}$$$ placed after the $$$N^{th}$$$ and the first one placed right after the $$$(N+1)^{th}$$$. These $$$N$$$ areas are vacancy and are available for one player to own it.
In a player turn, if he or she rolls the number $$$X$$$, he or she will move $$$X$$$ steps forward from his or her current position. Assume that he or she ends up in $$$Y^{th}$$$: if $$$Y=1$$$ or $$$Y$$$ is owned by this player before, then nothing happens, else if $$$Y$$$ is vacancy, the player will own the property, and if $$$Y$$$ is owned by the other player, $$$Y$$$ will have to pay the owner of the property.
Seo, B21 and Lowie have played one abnormal games: in the first $$$10^9$$$ turns for each player: Seo rolls exactly $$$V_s$$$, B21 rolls exactly $$$V_b$$$, and Lowie rolls exactly $$$V_l$$$ in every turn. Seo is the first person to move, then B21, then Lowie, then Seo again, and so on.
Before the first event of a person step on a property of another person and have to pay him, how many dice rolls has happened. If after $$$3*10^9$$$ turn, no one have to pay others, output $$$3000000000$$$.
The only line contains four integers: $$$N$$$, $$$V_s$$$, $$$V_b$$$ and $$$V_l$$$ ($$$3 \le N \le 10^5$$$, $$$1 \le V_s, V_b, V_l \le N$$$).
The only integer denotes the number of dice rolls happened before the event of a player pays another.
7 3 4 5
10
29 6 10 15
3000000000
Example 1:
Initial state of the game: all three players are at the government property:
After the first three rolls (one for each player), the game will look like this (blue indicates the property of Seo, purple indicates the property of B21, and yellow indicates the property of Lowie):
After the next three rolls (one for each player), the game will look like this (Seo is at $$$7$$$, B21 is at $$$1$$$, and Lowie is at $$$3$$$):
After the next three rolls:
The next roll will make Seo step on a property of B21 (property number $$$5$$$). That makes Seo have to pay an amount of rental fee to B21.
Example 2:
We can prove that in this test, players can only move on to government's property or their own properties, again and again, not others', so that after $$$10^9$$$ turns of infinite repetitions, three friends decided that they will be more productive and started to organize CP contests for their students.
This is an interactive problem
Low_ has a beautiful tree, which he keeps very carefully. A tree is a tree, but mathematically, it could be modeled as an indirect connected graph with no cycles. Suppose low_'s tree has $$$n$$$ nodes and $$$n-1$$$ edges.
S_e_o is low_'s friend, and he has been attracted to the Codeforces golden secret for a long time. He does not want to hurt his friend by taking it illegally, especially from his beloved tree, so S_e_o comes up with a devious plan. He hides the golden secret in a node of low_'s favorite tree and challenges him to find that node by interacting with an A.I bot which was created by another hacker named b21. There are two types of question that low_ could beg for:
"$$$?\;1\;u$$$": The bot will return number of edges on the simple path from node u to the hidden node.
"$$$?\;2\;u$$$": The bot will return the second node on the simple path from node u to the hidden node. If this type of query is asked for the hidden node by luck, the bot will return $$$0$$$.
Low_ does not want his friend to read his own secret to become master at Codeforces, so he has to be quick. Please help him, and remember to be quick by only asking no more than 36 queries.
The first line contains an integer $$$n$$$ ($$$1\le n\le 200000$$$).
The next $$$n-1$$$ lines, each contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$) denotes that there's an edge connects $$$u$$$ and $$$v$$$ in the tree.
You can make queries of type "? T u" to the robot. $$$T$$$ is either $$$1$$$ or $$$2$$$, and $$$1 \le u \le n$$$. The description for query is stated in the problem legend.
After the query read its result as an integer. If you read $$$-1$$$, that means your query is in the wrong format, or you have exceeded $$$36$$$ queries. Exit the program immediately to get the verdict "Wrong answer". If you don't, you might get an arbitrary verdicts.
When you find out the array, print "!" followed by a space and an integer denotes your answer. This is not counted as a query, but you only have one guess. If you failed to get the answer right, your verdict will be "Wrong answer".
After printing any query do not forget to output 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.
7 2 1 2 4 3 5 6 2 1 3 2 7 1 3 0
? 2 2 ? 1 6 ? 1 3 ! 3
Has someone ever said Vietnam is out of the effect of terrorism ?
Indeed, S_e_o, the current prime minister of Vietnam, is so proud that he has turned Vietnam into the safest area in the world, with no terrorism, unlike the U.S or France. However, he is not aware of a conspiracy to terrorize Vietnam by launching a series of Bomb right on Tran Duy Hung street, Hanoi.
However, a secret agent team has informed S_e_o about the terrorists' plan.
Tran Duy Hung street could be modeled as a segment $$$[1, 10^{9}]$$$ in the Ox axis. There are $$$n (1\le n\le 2000)$$$ bombs known to be located on distinct integer coordinates on the street. The government has only $$$P$$$ type-1 tools and $$$Q (0\le P, Q\le 10^{5})$$$ type-2 tools that could eliminate bombs. The difference between to type is that type-1 destroy bombs in a subsegment with length $$$w$$$, while type-2 could destroy in a subsegment of $$$2w$$$. However, each tool could only be used once.
At this time, HCW is going on, and HCW Organizing Committee just wonders the minimum $$$w (1\le w)$$$ that allows S_e_o to destroy the terrorists' plan. Now it turns out to be your duty to find the answer. It is guaranteed that S_e_o could always destroy the terrorism conspiracy to save Hanoi and Vietnam.
Line 1: 3 numbers $$$n,P, Q$$$
Line 2... $$$ n+1$$$: Each line contains a number $$$x$$$ indicates the location of a bomb.
Print a single number which is the answer.
3 1 1 2 11 17
4
Lowie is creating a new champion in the critically acclaimed game LoL (Land of Literacy). Named it Dahlia, he planned that the champion will have 4 different abilities. One of them is Pull 'em Over.
Long story short: Assuming that the map is a Cartesian plane (an $$$O-xy$$$ plane), Dahlia and the targets are small enough to be considered as points. When Pull 'em Over is activated, Dahlia throws her stretchy arms at a direction of her choice, and if there is any target in the direction with the distance not more than $$$R$$$ from her, Dahlia pull the first target she reaches towards her immediately.
Supposed that Dahlia is standing in position $$$(x_0, y_0)$$$. There are $$$N$$$ different target in the map. Without any movements from her and all of the targets, count the number of targets she can choose to Pull 'em Over.
The first line contains four integers: $$$x_0$$$, $$$y_0$$$, $$$R$$$, $$$N$$$. ($$$|x_0|, |y_0| \le 10^9$$$, $$$1 \le R \le 10^9$$$, $$$1 \le N \le 5*10^5$$$) - the coordinates of Dahlia, the radius she can cover, and the number of targets.
The $$$i$$$-th line of the next $$$N$$$ lines contain two integers: $$$x_i$$$ and $$$y_i$$$ - coordinates of the $$$i$$$-th target.
It is guaranteed that there are no two targets standing on a same position on the map, and there are no targets stand on the same position as Dahlia.
Output a single integer denotes your answer to the test - number of targets she can choose to Pull 'em Over.
0 0 10 4 1 2 4 1 -1 -2 3 -4
4
1 2 5 4 -2 -2 6 2 10 1 -2 1
3
With two Spear of Shojin and a Guinsoo's Rageblade, Pyke is dominating in the arena of Teamfight Tactics.
After bitterly lose to the team based on Glacial and Archers of Lowie's, B21 spent days and nights to research on the mystery of the champion Pyke. He found something interesting, (it might be a bug) but still can bring him great advantages in TFT games.
B21 found $$$N$$$ sets of attacks for Pyke. Each set consists of $$$A_i$$$ attacks. After completing set of attacks of index $$$i$$$, the attack speed of Pyke equals to minimum value between current attack speed and $$$B_i$$$ milliseconds for each attack. And to defeat Lowie, Pyke have to complete all $$$N$$$ sets of attacks. Help B21 find the minimum time Pyke complete all $$$N$$$ sets in milliseconds. Know that, at first Pyke have completed the first set of attacks.
The first line contains an integer $$$N$$$ ($$$1 \le N \le 10^5$$$).
The second line contains $$$N$$$ intergers $$$A_i$$$ ($$$1 \le A_i \le 10^6$$$).
The third line contains $$$N$$$ intergers $$$B_i$$$ ($$$1 \le B_i \le 10^6$$$).
It is guaranteed that $$$A_1 = 1$$$ and $$$B_n = 0$$$ and $$$A_1 \lt A_2 \lt ... \lt A_n$$$ and $$$B_1 \gt B_2 \gt ... \gt B_n$$$.
Print exactly one integer - the minimum time Pyke complete all $$$N$$$ sets in milliseconds.
5 1 2 3 4 6 5 4 3 1 0
26
6 1 2 3 8 9 10 5 4 3 2 1 0
45
In the first example, Pyke complete set of attacks of index $$$1, 4, 5, 2, 3$$$ respectively or index $$$1, 4, 5, 3, 2$$$.
In the second example, Pyke complete set of attacks of index $$$1, 3, 6, 2, 4, 5$$$ respectively or index $$$1, 3, 6, 2, 5, 4$$$, ......
Poor them!
Whenever rain season comes, the water rises as hell and the most affected region is Northwest Vietnam. Villages, houses, plants, animals, and people are all victims of cruel Nature.
S_e_o is a civil manager of Northwest Vietnam. As a man with a kind heart, he worries for Northwestern citizens and is willing to do everything to stop the disaster. With only a computer, he roughly models the area of Northwest Vietnam on Cartesian plane. The model is a polyline with n points, each with integer coordinates. He wants to calculate the maximum area that could be filled with water, but his computer breaks down right after he has finished the model. He still keeps the input data and calls for your help!
Please help him !!
The first line contains an integer $$$\ n\ (2\le n\le {10}^5)$$$ , the number of points in the polyline
Line 2..$$$\ n+1$$$ : Line $$$i$$$ contains two numbers $$$x_i,\ y_i(0\le x_i,\ y_i\le {10}^6)$$$ which are x-coordinates and y-coordinates of a point.
It is guaranteed that $$$x_i \lt x_{i+1}$$$
Output: A single line contains a single real number which is the answer. Your output is correct if the difference between your output and the test answer is no larger than $$${10}^{-6}$$$
7 1 1 2 0 3 1 5 5 7 2 8 3 9 0
1.8333333
The following image explains the first sample test case
The rivalry of Lowie and B21 have history. That's how the HNOI Civil War was found.
Both are challenged to a contest called: "Who Can Get His Tree Higher?". As straightforward as it sound: Lowie and B21 bring their own trees and get to pick a node of choice as the root, the one who gets his tree to have the greater height of wins the the contest.
To revise: A tree is a connected bidirectional graph with N vertices and N-1 edges. The height of one tree is the greatest distance from the root to one of its leaves. A distance between two nodes on a tree is the number of nodes that are on the simple path between those two nodes.
B21 is a master of trees. He knows how to make the optimal move to make the height of his tree as great as possible by choosing the best root. Meanwhile, Lowie doesn't know it. Lowie will choose a random node to be the root of his tree.
Nevertheless, B21's tree is still way smaller than Lowie's one, so even with an optimal move, B21 would still cannot win this contest. Your job is to show B21 if he still stand any chance to win this contest. A draw is a draw, which means neither player won, and they will find another contest to compete in.
The first line contains an integer: $$$N$$$ ($$$1 \le N \le 10^5$$$) - number of nodes in B21's tree.
The next $$$N$$$ lines, each contains $$$2$$$ integers: $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le N$$$) - denotes that there is an edge connects node $$$u$$$ and node $$$v$$$ in B21's tree.
The next line contains an integer: $$$M$$$ ($$$N \lt M \le 2*10^5$$$) - number of nodes in Lowie's tree.
The next $$$M$$$ lines, each contains $$$2$$$ integers: $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le N$$$) - denotes that there is an edge connects node $$$u$$$ and node $$$v$$$ in Lowie's tree.
If B21 stand a chance to win, output "GGEZ". Otherwise, output "FF".
5 1 2 1 3 2 4 2 5 7 1 2 2 5 3 6 2 4 1 3 3 7
GGEZ
5 1 2 1 3 2 4 2 5 7 1 2 1 3 3 4 4 5 2 6 6 7
FF
In both sample tests, B21 will obtain the maximum height of his tree if he chooses node $$$4$$$ as the root of his tree:
The height of this tree is now $$$4$$$.
In the first example, B21 will win if Lowie choose node $$$1$$$ as the root:
In the second example, even after Lowie made the worst choice of root, the contest would still be a draw, that means B21 cannot win in any way:
"Houston, are you there? Over."
"Yes. Over."
"It seems like there is something wrong with our spaceship. Something has got into the ranch near the pointy tip of our spaceship and it is too far for us to put a hand on it. Over."
"Copy. There is a metal stick inside the storage of the spaceship. It has been broken down into several pieces for it to be easy to store in the spaceship. You can use it to poke the thing down. Over."
"Got it. But how do we assemble it back to one piece? Over."
"See the numbers that is written on the two ends. Two ends of two pieces can connect if the numbers written on it is the same. The stick can only be used if all $$$N$$$ pieces are assembled back together. Over."
"So it works like the game "Domino"? Over."
"True. Over."
You are given all of the $$$N$$$ pieces of the sticks, with numbers given for each end of each stick. You have to output one way to put the pieces back together out of possibly many answers. It is guaranteed that there are at least one possible answer.
The first line contains an integer $$$N$$$ ($$$2 \le N \le 8$$$) - number of pieces that the stick broken down into.
The $$$i$$$th line of the next $$$N$$$ lines contains two integer $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le 6$$$) - numbers written on two ends of piece $$$i$$$.
Output $$$N$$$ lines. The $$$j$$$th line contain two items: an integer $$$i$$$, and a letter $$$c$$$. The integer $$$i$$$ indicates that you use the $$$i$$$th piece in the $$$j$$$-th place in the configuration, and the letter $$$c$$$ indicates that if you decide to put it in the same order as the input ($$$c=$$$'a' for this case) or if you want to reverse it ($$$c=$$$'b' for this case).
You can output any configuration you want, but you have to make sure that the ends that connect to each other have the same number. Otherwise, you'll get "Wrong Answer".
2 3 2 6 3
2 a 1 a
5 3 2 4 5 4 4 5 1 3 1
3 b 2 a 4 a 5 b 1 a
First example: $$$(2, 3)-(3, 6)$$$.
Second example: $$$(4, 4)-(4, 5)-(5, 1)-(1, 3)-(3, 2)$$$. The first line you can print "3 a" instead.
If you have ever enjoyed the classic Plants vs Zombies to the very end of it, surely you have come across a special type of plant in this game: Imitater. If you choose this plant to be with you for a round, it can imitate any kind of plant you want, including its abilities, its stats and even its cost, so you'll have one more slot of that plant for the whole round, double the trouble!
Lowie came across an Imitater and challenge it for a game of cards drawing.
$$$N$$$ stack of cards are on the table. The $$$i$$$th stack on the table contains $$$A_i$$$ cards. In each move:
- A player can draw one card from any stack on the table (if it's not empty).
- A player can draw one card from each of every stack on the table (if no stack is empty).
The winner is the one that drawn the last card on the table.
Of course, as a master in game theory, Lowie knows the optimal strategy to win this game. But Imitater has copied Lowie, so that both are having exactly the same intelligence and the same winning tactics in their mind.
So, given the state of the game, who would win, if Lowie gets to go first?
First line: an integer $$$N$$$ ($$$1 \le N \le 1000$$$) - number of stacks.
Second line: $$$N$$$ integers: $$$A_1, A_2, ..., A_N$$$ ($$$1 \le A_i \le 1000$$$) - number of cards in each stacks.
Output "lowie" if Lowie wins the game, or "imitater" if Imitater the Potato wins.
2 1 2
lowie
3 1 4 3
imitater
Seo is an expert in electronics (as well as codeforces). Also, he is a very very good friend of B21.
One time, B21 call him for help: the electricity board that shows the distance between Earth and the nearest black hole in nanometres has a glitch. As B21 said: there were two "jumpity digits" that made the numbers display on the board became false.
Right now, the number on the board is $$$X$$$. B21 states that the number that must be displayed on the board is smaller than $$$X$$$, and as optimistic as the person B21 is, he states that it should be the greatest possible number.
Help Seo find the number that must be displayed, or determine that it is impossible, which means there were some fallacies in B21's statements.
The only line in the input contains an integer: $$$X$$$ ($$$1 \le X \le 10^{100}$$$) - the number that is displaying on the board.
Print "-1" if it is impossible to find the number. Else, print that number on a single line.
354
345
999
-1
100
-1
11101
11011
2
-1
This is an interactive problem.
Lowie went to a Science fair. His favorite section in the fair is the "interaction" zone, where people spend money to play games and win prizes in different booths.
Lowie went to the Prime booth, where he can win sorted prime array. The boothkeeper B21 kept a prime array secret from Lowie, and he have to guess the whole array by buying queries from B21.
For each queries, Lowie can ask for a subsegment (i.e.: a series of consecutive elements) $$$[l, r]$$$ in the array, B21 will return him with the product of all elements in the subsegment, modulo $$$10^9+9$$$. A query for a subsegment $$$[l, r]$$$ will cost Lowie exactly $$$\frac{1}{(r-l+1)^2}$$$ BTC.
Lowie only have $$$0.45$$$ BTC, help him win the Prime array. Please notice that the array is sorted, and you can ask as many queries as you want, as long as the total cost doesn't exceed the amount that Lowie has.
Oh, and the boothkeeper B21 doesn't like big numbers, so his array will consists only primes in the range of $$$[1, 10^4]$$$.
Read an integer $$$N$$$ - length of the array. $$$2 \le N \le 500$$$.
You can make queries of type "? l r" to ask B21 the product of all elements in the segment $$$[l, r]$$$ ($$$1 \le l \le r \le N$$$) modulo $$$10^9+9$$$.
After the query read its result as an integer. If you read $$$-1$$$, that means your query is not correct, or you have exceeded the total amount of money that you have. Exit the program immediately to get the verdict "Wrong answer". If you don't, you might get an arbitrary verdicts.
When you find out the array, print "$$$!$$$" followed by a space. Then, print $$$N$$$ integers, separated by spaces. This is not counted as a query and will have the cost of $$$0$$$, but you only have one guess. If you failed to get the answer right, your verdict will be "Wrong answer".
After printing any query do not forget to output 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.
5 14322 341
? 1 5 ? 4 5 ! 2 3 7 11 31
Example 1:
Ask for query: $$$[1, 5]$$$, get the answer of $$$14322$$$.
Ask for query: $$$[4, 5]$$$, get the answer of $$$341$$$.
Somehow got the answer right :/
Last Sunday, B21 still cannot escape from the haunting memory of "Gate D" in Hanoi - Amsterdam High School. He felt lost between a mob of strangers, and he was worried about his students, stuck inside the horrifyingly terrible lab of this school.
Even at night, he still had bad dreams about that day. He stuck in a one-dimensional array of integers with absolutely no sign of people. Around him, the "ghosts" of Lowie and Seo still fly around, whisper to his ears some crap like: "Hanoi-Ams is better than NH High School", or "Our students can still outperform with 1 Gb of Random Access Memory computers", etc. .
The array is one-dimensional, so B21 can move forward or backward (a.k.a. left or right in some other manner). From position $$$i$$$, he can move forward to position $$$i+1$$$ or backward to $$$i-1$$$ if he is able to. Luckily, he didn't forget to dream that he get a superpower of some kind. This time: he can teleport! B21 can teleport from $$$i$$$ to $$$j$$$ only if the number written on position $$$i$$$ is equal to the number written on position $$$j$$$.
Each move forward takes B21 $$$R$$$ unit(s) of energy. Each move backward takes $$$L$$$ unit(s). And if he uses teleport, it will take him $$$C$$$ unit(s) of energy.
He want to get back to his dear Nguyen Hue High School to get more superpowers to rescue his students. Gate D (starting point) is located at position $$$u$$$ on the array, and his school (destination) is located at position $$$v$$$ on the array. What is the least amount of energy does it take for B21 to reach his destination?
First line: four integers $$$N$$$ ($$$2 \le N \le 10^5$$$) - size of the array, $$$L$$$, $$$R$$$ and $$$C$$$ ($$$1 \le L, R, C \le 10^9$$$) - cost of energy for each kind of movement.
Second line: two integers: $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le N$$$) - the position of Gate D, and the position of NH High School.
Third line: $$$N$$$ integers: $$$A_1, A_2,...,A_N$$$ - elements of the array. All elements in the array is in range $$$[1, 10^9]$$$
The only line contains a single integer: the minimum energy needed to reach the destination.
5 1 2 3 1 5 1 2 1 1 2
5
5 1 4 3 3 5 1 2 1 1 2
4
In the first example, B21 moves forward and then teleports to position $$$5$$$. The total units of energy are $$$2 + 3 = 5$$$.
In the second example, B21 moves backward and then teleports to position $$$5$$$. The total units of energy are $$$1 + 3 = 4$$$.