Cookie Sigma is ready to play some Clash Royale! Before he can battle for trophies, he must build his deck.
He is given two arrays of size $$$n$$$ $$$(4 \leq n \leq 100)$$$, $$$a$$$ and $$$b$$$. Each index $$$i$$$ $$$(1 \leq i \leq n)$$$ represents a pair of cards with elixir costs $$$a_i$$$ and $$$b_i$$$.
To build his deck, Cookie Sigma must follow these rules:
- He cannot add individual cards—he must choose an index $$$i$$$ and add both cards $$$a_i$$$ and $$$b_i$$$ to his deck.
- He cannot choose the same index more than once.
- A Clash Royale deck must contain exactly $$$8$$$ cards, so he must select 4 distinct indices in total.
Cookie Sigma loves cycle decks and wants to minimize the total elixir cost of his deck. Help him determine the minimum possible total elixir cost of any valid deck he can create!
The first line contains an integer $$$n$$$ $$$(4 \leq n \leq 100)$$$, the size of $$$a$$$ and $$$b$$$.
The second line contains $$$n$$$ integers, $$$[a_1, a_2, ... a_n]$$$ $$$(1 \leq a_i \leq 1000$$$), the elements in $$$a$$$.
The third line contains $$$n$$$ integers, $$$[b_1, b_2, ... b_n]$$$ $$$(1 \leq b_i \leq 1000$$$), the elements in $$$b$$$.
Output one number, the minimum possible total elixir cost of a valid deck Cookie Sigma can create. Note that this is the total cost of his deck (the sum of elixir of all cards in his deck), NOT the average elixir cost.
64 3 9 2 9 21 3 8 3 1 5
23
In the example test case, it is optimal for Cookie Sigma to pick indices $$$1, 2, 4, 6$$$ and add the cards at these indices to his deck. By doing this, his deck will consist of cards with elixir costs $$$[1, 2, 2, 3, 3, 3, 4, 5]$$$. Summing these up, we can see that the total elixir cost of his deck is 23 elixir.
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. If your P.E.K.K.A. can survive the battle and destroy the opponent's, output "YES". Otherwise, output "NO."
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}$$$).
If your P.E.K.K.A. can kill the opponent's P.E.K.K.A. and stay alive, output "YES". Else, output "NO".
5 20 3 30
YES
3 12 2 20
NO
9 9 9 9
NO
In the first test case, your P.E.K.K.A. wins after 6 swings. It survive on 2 health points. In the second test case, your P.E.K.K.A. dies after 6 swings. The opponent P.E.K.K.A. still has 2 health points. In the third test case, both of your P.E.K.K.A.'s die after the first swing. You need to survive, so the answer is "NO".
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.