Nick's favorite card is Mega Knight. His favorite part about the Mega Knight is that he can drop it on anyone, anywhere, at anytime.
Obviously, Nick wants to maximize the value of his Mega Knight. The Mega Knight can hit a $$$+$$$-shaped region. That is, if we pick a center square that the Mega Knight is dropped on, the Mega Knight also hits the squares directly North, South, East, and West of it.
Given the Clash Royale map represented by a grid with $$$n$$$ rows and $$$m$$$ columns, calculate the maximum value Nick can get by dropping his Mega Knight.
The first line contains two integers, $$$n$$$ and $$$m$$$ ($$$1 \leq n,m \leq 100$$$).
The next $$$n$$$ lines each contain $$$m$$$ space-separate integers, with each integer $$$v$$$ ($$$1 \le v \le 100$$$) representing the value Nick can obtain from his Mega Knight hitting each grid spot.
Please calculate the maximum value Nick can get from his Mega Knight.
3 3 1 0 0 0 0 1 0 1 1
3
1 4 2 1 2 1
5
In the first sample test, Nick should play the mega knight in the bottom right corner.
In the second sample test, Nick should play the mega knight in the second tile from the left.
Edward is playing the sneaky golem deck. He just finished a game and you have the log of the actions (cards he played) in the game. You really want to know whether or not he played his sneaky golem, but because golem is so sneaky, the transcript does not show the golem. Thus, you will do the next best thing: use the game log to find out if it was ever possible that Edward played his sneaky golem. The sneaky golem costs $$$G$$$ elixir.
The game log is an array of $$$T$$$ non-negative integers, denoting how much elixir Edward spent at each timestep. This game log does not capture any possible elixir spent playing the golem.
Between each timestep, Edward gains $$$1$$$ elixir. Edward can have a maximum of $$$E$$$ elixir. He starts at the first timestep with $$$E$$$ elixir. He can never have more than $$$E$$$ elixir, nor can he have negative elixir.
Please find if it was possible that at any point in the game, Edward played his sneaky golem.
The first line contains $$$T$$$, $$$E$$$, and $$$G$$$. $$$1 \leq T \leq 10^5$$$, $$$1 \leq E \leq 10^9$$$, $$$1 \leq G \leq E$$$.
The second line contains $$$T$$$ integers, $$$t_1, t_2, ..., t_T$$$, where $$$t_i$$$ represents the elixir spent at timestep $$$i$$$, excluding any sneaky golem plays. $$$0 \leq t_i \leq E$$$.
It is guaranteed that this sequence is valid (Edward's elixir never goes negative).
Output $$$YES$$$ if it was possible that Edward played his sneaky golem, $$$NO$$$ otherwise.
4 10 8 2 0 0 3
YES
1 10 8 5
NO
In the first test case, Edward could have played his sneaky golem at the first timestep. Then, he would have 3 elixir by the 4th timestep, which is valid.
In the second test case, there is only one opportunity for Edward to play his sneaky golem, at the first timestep. However, doing so needs 13 elixir, which will cause Edward to go negative. Edward cannot have negative elixir so this cannot have happened. Thus, unfortunately, it is not possible for sneaky golem's time to have come.
Warith barely plays Clash Royale, so not only can he not come up with good flavortext, but he's completely terrible at the game. It's gotten to the point where he uses a Mega Knight deck to help him win all his games...
Anyway, Warith wants to figure out how fast Mega Knight can move in order to optimize his deck. He figures out that Mega Knight can walk at a pace of $$$a$$$ units per second. He's also able to charge up and leap a distance of $$$b$$$ units, but this takes him $$$3$$$ seconds due to the charging and travel distance. Given a distance $$$n$$$ to travel, where the card starts at $$$x = 0$$$ at $$$t = 0$$$, can you find how long it takes Mega Knight to travel if he moves optimally? Note that if Mega Knight ever oversteps he will be under fire, so he must travel exactly $$$n$$$ meters.
The input consists of a single line of three integers: the walking pace $$$a$$$, the leaping distance $$$b$$$, and the total distance to travel $$$n$$$. The following constraints are given:
- $$$10 \le n \le 10^{18}$$$
- $$$1 \le a,b \le n$$$
- $$$b \ge 2a$$$
Output a single integer $$$t$$$, the minimum time in seconds it takes for Mega Knight to travel $$$n$$$ units. If it is impossible for him to travel exactly $$$n$$$ meters, print $$$-1$$$.
1 2 10
10
2 4 11
-1
In the first case, it is optimal to just walk $$$10 \cdot 1$$$ units in $$$10$$$ seconds, rather than use a leap at all.
In the second case, it is impossible to travel $$$11$$$ units with a walking pace of $$$2$$$ and a leap of $$$4$$$.
The only difference between this problem and the hard version is the constraints on $$$n$$$, $$$k$$$, and $$$m$$$.
In Clash Royale 2, instead of there being 1 layer of bridges, there are now $$$n$$$ layers of bridges. While playing the game, your King Tower is located at the origin, $$$(0,0)$$$, the $$$i^\text{th}$$$ layer of bridges is located at $$$y=l_i$$$, and the enemy King Tower is located on the other side of the playing field at $$$(0,m+1)$$$. There are also $$$k$$$ bridges, with the $$$j^\text{th}$$$ bridge located at a single point, $$$(x_j, l_{y_j})$$$, each of which has a debuff value, $$$d_j$$$.
Bandit wants to cross from your King Tower to the enemy King Tower by dashing as quickly as possible. Initially, Bandit has a debuff of $$$1$$$. When dashing, Bandit can only do $$$1$$$ of the following actions:
- Dash from your King Tower to a bridge in layer $$$1$$$.
- Dash from a bridge in layer $$$i$$$ to a bridge in layer $$$i+1$$$ (only if $$$1\le i \lt n$$$).
- Dash from a bridge in layer $$$n$$$ to the enemy King Tower.
If the Bandit dashes to bridge $$$j$$$, Bandit's debuff now becomes $$$d_j$$$. If Bandit dashes from $$$(x_1,y_1)$$$ to $$$(x_2,y_2)$$$, then it takes $$$D\cdot \left|x_1-x_2\right|\cdot \left|y_1-y_2\right|$$$ seconds, where $$$D$$$ is Bandit's debuff before dashing. Crossing a bridge takes $$$0$$$ seconds.
Given the layout of the playing field, help Bandit find the minimum time it takes to dash from your King Tower to the enemy King Tower. It is guaranteed that every bridge is on a layer and that every layer has at least $$$1$$$ bridge. It is also guaranteed that no $$$2$$$ bridges are at the exact same coordinates.
The first line of input contains $$$n$$$, $$$k$$$, and $$$m$$$ ($$$1\le n\le k, m\le 5\cdot10^3$$$) — the number of layers of bridges, the number of bridges, and the length of the playing field, respectively.
The next line of input contains $$$n$$$ numbers, $$$l_1, l_2, \ldots ,l_n$$$ ($$$1\le l_1 \lt l_2 \lt \cdots \lt l_n \le m$$$) — the $$$y$$$-levels of the bridge layers.
The $$$j^\text{th}$$$ of the next $$$k$$$ lines contains $$$3$$$ space-separated integers, $$$x_j$$$, $$$y_j$$$, and $$$d_j$$$ ($$$-10^6\le x\le10^6, 1\le y_j\le n, 1\le d_j\le10^6$$$) — the $$$x$$$-coordinate of the $$$j^\text{th}$$$ bridge, the index of the bridge layer it belongs to, and the debuff of the bridge, respectively. It is guaranteed that every bridge is on a layer and that every layer has at least $$$1$$$ bridge. It is also guaranteed that no $$$2$$$ bridges are at the exact same coordinates.
Output a single integer, the minimum time, in seconds, it takes for Bandit to dash from your King Tower to the enemy King Tower.
3 5 51 2 5-3 1 3-1 3 20 2 101 3 42 2 1
25
Bandit starts at $$$(0,0)$$$, your King Tower, with a debuff of $$$1$$$.
Bandit can then dash from $$$(0,0)$$$ to bridge $$$1$$$, located at $$$(-3,1)$$$. This takes $$$1\cdot \left|0-(-3)\right|\cdot\left|0-1\right| = 3$$$ seconds to complete. This also updates Bandit's debuff to $$$3$$$.
Bandit can then dash from $$$(-3,1)$$$ to bridge $$$5$$$, located at $$$(2,2)$$$. This takes $$$3\cdot\left|-3-2\right|\cdot\left|1-2\right| = 15$$$ seconds to complete. This also updates Bandit's debuff to $$$1$$$.
Bandit can then dash from $$$(2,2)$$$ to bridge $$$4$$$, located at $$$(1,5)$$$. This takes $$$1\cdot\left|2-1\right|\cdot\left|2-5\right| = 3$$$ seconds to complete. This also updates Bandit's debuff to $$$4$$$.
Bandit can then dash from $$$(1,5)$$$ to the enemy King Tower, located at $$$(0,6)$$$. This takes $$$4\cdot\left|2-1\right|\cdot\left|5-6\right|=4$$$ seconds to complete.
This entire journey takes $$$3+15+3+4=25$$$ seconds to complete. It can be proven that this is the shortest time possible.
An opponent's P.E.K.K.A. with $$$a_2$$$ attack points and $$$h_2$$$ health points is coming straight for your tower! You quickly deploy your own P.E.K.K.A., with $$$a_1$$$ attack points and $$$h_1$$$ health points. The P.E.K.K.A.'s will battle each other, swinging at each other at the exact time every second until one or both dies. Every swing, your P.E.K.K.A. will remove $$$a_1$$$ health points from your opponent's, and your opponent's P.E.K.K.A. will remove $$$a_2$$$ health points from yours. A P.E.K.K.A. dies when it reaches 0 or less health points. You are unsure if your P.E.K.K.A. can win this battle. Fortunately, you have the Royal Chef on your side! He can feed Pancakes to your P.E.K.K.A. before the battle, making it stronger. For every Pancake, you can choose to increase your P.E.K.K.A.'s attack by 1, or health by 1. Calculate the minimum number of Pancakes the Royal Chef must cook for your P.E.K.K.A. to survive this battle!
The input contains four integers $$$a_1$$$, $$$h_1$$$, $$$a_2$$$, $$$h_2$$$ ($$$1 \le a_1, h_1, a_2, h_2 \le 10^{9}$$$).
Output the minimum number of Pancakes the Royal Chef must cook for your P.E.K.K.A.. If your P.E.K.K.A. is already strong enough to survive the battle, output 0.
4 10 8 12
8
7 7 12 20
19
4 6 2 17
3
1 1 1 100
19
In the first test case, it is optimal to make 8 pancakes. Use all 8 pancakes to increase attack. After the first round of attacks, your P.E.K.K.A. wins with 2 health points remaining.
In the second case, it is optimal to make 19 pancakes. Use 13 on attack, and 6 on health. After the first round of attacks, your P.E.K.K.A. wins with 1 health point remaining.
In the third case, it is optimal to make 3 pancakes. Use 2 on attack, and 1 on health. After the third round of attacks, your P.E.K.K.A. wins with 1 health point remaining.
This is an interactive problem. You have to use a flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout), in Java — System.out.flush(), in Pascal — flush(output) and in Python — sys.stdout.flush().
Bobob has developed a new and improved rocket cycle deck that exploits the overwhelming force of rockets to annihilate his opponents' towers. There's only one problem: he knows the enemy's two princess towers are horizontally aligned with each other, but he needs your help to find their exact x-coordinates.
In order to find the x-coordinates of the princess towers $$$x_1$$$ and $$$x_2$$$ ($$$1 \le x_1 \lt x_2 \le n$$$), you can place down hog riders. Each hog rider can be placed at an x-coordinate by printing a single integer from $$$1$$$ to $$$n$$$. Flush output stream after printing each x-coordinate. Hog riders will target the nearest tower (or the right tower if halfway in between), earning one of three possible responses:
- the string "<" (without quotes), if the closest princess tower is to the left of the hog rider ($$$x_{tower} \lt x_{hog}$$$);
- the string ">" (without quotes), if the closest princess tower is to the right of the hog rider ($$$x_{tower} \gt x_{hog}$$$);
- the string "=" (without quotes), if the hog rider is on top of a princess tower ($$$x_{tower} = x_{hog}$$$).
The closest princess tower $$$x_{tower}$$$ is determined to be $$$x_1$$$ if $$$|x_{hog} - x_1| \lt |x_{hog} - x_2|$$$, and $$$x_2$$$ otherwise.
When you figure out the x-coordinates of the two princess towers, print string "! x1 x2", where $$$x1$$$ and $$$x2$$$ are the x-coordinates of the princess towers from left to right ($$$x1 \lt x2$$$), and terminate your program normally immediately after flushing the output stream.
You only have 500 elixir, and each hog rider costs 4 elixir, so you are allowed to place no more than 125 hog riders (not including printing the princess towers' coordinates at the end).
Use standard input to read the responses to the hog riders.
The first line contains an integer $$$n$$$ ($$$2 \le n \le 10^9$$$) — the maximum possible x-coordinate.
The following lines will contain responses to your hog riders — strings "<", ">" or "=". The $$$i$$$-th line is a response to your $$$i$$$-th hog rider. When you are ready to guess the princess towers' coordinates, print "! x1 x2" and terminate your program.
The game will allow you to read the response to the hog rider only after your program prints the hog rider's x-coordinate and performs the flush operation.
To print the hog riders' coordinates, your program must use standard output.
Your program must print the hog riders' x-coordinates — integer numbers $$$x$$$ ($$$1 \le x \le n$$$), one query per line (do not forget "end of line" after each $$$x$$$). After printing each line your program must perform the flush operation. When you are ready to guess the princess towers' coordinates, print "! x1 x2", flush, and terminate your program.
10
<
=
>
=
4
1
5
9
! 1 9
In this example, the princess towers are located at x-coordinates $$$1$$$ and $$$9$$$.
Placing a hog rider at an x-coordinate of $$$4$$$ will result in it targeting the princess tower at $$$1$$$ because $$$|4-1| \lt |4-9|$$$, so the response is "<".
Placing a hog rider at an x-coordinate of $$$1$$$ will be on top of a princess tower, so the response is "=".
Placing a hog rider at an x-coordinate of $$$5$$$ will result in it targeting the princess tower at $$$9$$$ because $$$|5-9| \ge |5-1|$$$, so the response is ">".
Placing a hog rider at an x-coordinate of $$$9$$$ will be on top of a princess tower, so the response is "=".
The player correctly guesses that the princess towers are at x-coordinates $$$1$$$ and $$$9$$$, and the program terminates.
The developers of Clash Royale are currently experimenting with the Mortar card. Rather than targeting the nearest enemy, Mortars target the closest enemy which is at least some distance $$$d$$$ away. For performance reasons, the developers define distance using Manhattan distance – in particular, the Manhattan distance between two points $$$(x, y)$$$ and $$$(x', y')$$$ is defined as $$$|x' - x| + |y' - y|$$$.
In their test simulation, the developers have $$$n$$$ of these Mortars numbered from $$$0$$$ to $$$n - 1$$$ on a two-dimensional grid, and for the purposes of testing, each Mortar considers all other Mortars to be enemies. However, the developers are struggling to efficiently compute which Mortar each Mortar will target, leading the simulation to stall. Can you help them compute the targets more efficiently?
Warning: Python solutions may struggle to pass test cases due to the time limit.
The first line contains two integers $$$n$$$ and $$$d$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le d \le 10^9$$$) – the number of Mortars and the minimum distance threshold, respectively.
The next $$$n$$$ lines each contain two integers, with the $$$i$$$-th line containing $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i \le 5 \cdot 10^8$$$, $$$0 \le y_i \le 5 \cdot 10^8$$$) – the x-coordinate and the y-coordinate of the $$$i$$$-th Mortar, respectively. The locations of the Mortars are not necessarily distinct.
Output $$$n$$$ space-separated integers, where the $$$i$$$-th integer is the number of the Mortar that the $$$i$$$-th Mortar will target. If the $$$i$$$-th Mortar has no target, output $$$-1$$$, and if there are multiple potential targets which are equally close to the Mortar, output the smallest numbered target.
4 40 02 22 14 0
1 0 -1 0
For the sample test case, Mortar $$$0$$$ can target Mortars $$$1$$$ and $$$3$$$. Since both are equally close, Mortar $$$0$$$ targets Mortar $$$1$$$. Applying a similar procedure to the other Mortars, it can be seen that Mortar $$$1$$$ targets Mortar $$$0$$$, Mortar $$$2$$$ does not have any target, and Mortar $$$3$$$ targets Mortar $$$0$$$.
In Clash Royale 2, instead of there being 1 layer of bridges, there are now $$$n$$$ layers of bridges. While playing the game, your King Tower is located at the origin, $$$(0,0)$$$, the $$$i^\text{th}$$$ layer of bridges is located at $$$y=l_i$$$, and the enemy King Tower is located on the other side of the playing field at $$$(0,m+1)$$$. There are also $$$k$$$ bridges, with the $$$j^\text{th}$$$ bridge located at a single point, $$$(x_j, l_{y_j})$$$, each of which has a debuff value, $$$d_j$$$.
Bandit wants to cross from your King Tower to the enemy King Tower by dashing as quickly as possible. Initially, Bandit has a debuff of $$$1$$$. When dashing, Bandit can only do $$$1$$$ of the following actions:
- Dash from your King Tower to a bridge in layer $$$1$$$.
- Dash from a bridge in layer $$$i$$$ to a bridge in layer $$$i+1$$$ (only if $$$1\le i \lt n$$$).
- Dash from a bridge in layer $$$n$$$ to the enemy King Tower.
If the Bandit dashes to bridge $$$j$$$, Bandit's debuff now becomes $$$d_j$$$. If Bandit dashes from $$$(x_1,y_1)$$$ to $$$(x_2,y_2)$$$, then it takes $$$D\cdot \left|x_1-x_2\right|\cdot \left|y_1-y_2\right|$$$ seconds, where $$$D$$$ is Bandit's debuff before dashing. Crossing a bridge takes $$$0$$$ seconds.
Given the layout of the playing field, help Bandit find the minimum time it takes to dash from your King Tower to the enemy King Tower. It is guaranteed that every bridge is on a layer and that every layer has at least $$$1$$$ bridge. It is also guaranteed that no $$$2$$$ bridges are at the exact same coordinates.
The first line of input contains $$$n$$$, $$$k$$$, and $$$m$$$ ($$$1\le n\le k,m\le 10^6$$$) — the number of layers of bridges, the number of bridges, and the length of the playing field, respectively.
The next line of input contains $$$n$$$ numbers, $$$l_1, l_2, \ldots ,l_n$$$ ($$$1\le l_1 \lt l_2 \lt \cdots \lt l_n \le m$$$) — the $$$y$$$-levels of the bridge layers.
The $$$j^\text{th}$$$ of the next $$$k$$$ lines contains $$$3$$$ space-separated integers, $$$x_j$$$, $$$y_j$$$, and $$$d_j$$$ ($$$-10^6\le x\le10^6, 1\le y_j\le n, 1\le d_j\le10^6$$$) — the $$$x$$$-coordinate of the $$$j^\text{th}$$$ bridge, the index of the bridge layer it belongs to, and the debuff of the bridge, respectively. It is guaranteed that every bridge is on a layer and that every layer has at least $$$1$$$ bridge. It is also guaranteed that no $$$2$$$ bridges are at the exact same coordinates.
Output a single integer, the minimum time, in seconds, it takes for Bandit to dash from your King Tower to the enemy King Tower.
3 5 51 2 5-3 1 3-1 3 20 2 101 3 42 2 1
25
Bandit starts at $$$(0,0)$$$, your King Tower, with a debuff of $$$1$$$.
Bandit can then dash from $$$(0,0)$$$ to bridge $$$1$$$, located at $$$(-3,1)$$$. This takes $$$1\cdot \left|0-(-3)\right|\cdot\left|0-1\right| = 3$$$ seconds to complete. This also updates Bandit's debuff to $$$3$$$.
Bandit can then dash from $$$(-3,1)$$$ to bridge $$$5$$$, located at $$$(2,2)$$$. This takes $$$3\cdot\left|-3-2\right|\cdot\left|1-2\right| = 15$$$ seconds to complete. This also updates Bandit's debuff to $$$1$$$.
Bandit can then dash from $$$(2,2)$$$ to bridge $$$4$$$, located at $$$(1,5)$$$. This takes $$$1\cdot\left|2-1\right|\cdot\left|2-5\right| = 3$$$ seconds to complete. This also updates Bandit's debuff to $$$4$$$.
Bandit can then dash from $$$(1,5)$$$ to the enemy King Tower, located at $$$(0,6)$$$. This takes $$$4\cdot\left|2-1\right|\cdot\left|5-6\right|=4$$$ seconds to complete.
This entire journey takes $$$3+15+3+4=25$$$ seconds to complete. It can be proven that this is the shortest time possible.