Blackbeard is looking for sailors for his latest voyage! Given his fame and recognition, he got lots of volunteers when he decided to spread the word in the town of Caracas. However, Blackbeard realizes each sailor will get less of the $$$G$$$ total gold coins as he gets more sailors! Given that a sailor will mutiny if they receive less than $$$M$$$ coins, determine the maximum number of sailors that Blackbeard can have on his voyage if he does not want any soldier to mutiny!
The first line of input will contain two integers $$$M$$$ $$$(1 \le M \le 10^4)$$$, $$$G$$$ $$$(1 \le G \le 10^6)$$$, where $$$M \lt G$$$.
Output $$$S$$$, the maximum number of sailors Blackbeard can have in total given that he does not want any mutiny.
5 18
3
For purposes of self-defense and of course raiding other ships, cannons on board are essential to any pirate fleet. Jeanne de Clisson is taking inventory of the cannons on her flagship My Revenge, noting how many are currently lined up on both the port and starboard sides. However, cannons can be heavy enough to weigh down a ship, and if balanced incorrectly, they can potentially tip it over in the water! Help Jeanne analyze the layout of cannons on her ship and determine if they are in balance.
The first line of input contains two space-separated integers $$$W$$$ ($$$1 \leq W \leq 1000$$$), denoting the weight of each cannon, and $$$D$$$ ($$$1 \leq D \leq 10^9$$$), denoting the maximum weight difference allowed between the two sides of the ship in order for it to be considered balanced.
Then the second line of input contains two integers $$$C_p$$$ and $$$C_s$$$ ($$$1 \leq C_p, C_s \leq 10^6$$$), denoting the number of cannons currently lined on the port and starboard sides of the ship respectively.
If the port and starboard sides of the ship are already balanced, print In balance. If they are not in balance but cannons on either side could be moved across to produce a balanced configuration, print Move cannons. Otherwise, print Impossible.
6 6 1 6
Move cannons
4 4 7 8
In balance
Monkey D. Luffy has found the last clue necessary to pinpoint the location of the legendary One Piece! The clue is an unusual treasure map; it only has four scrawled integers $$$x_1, y_1, x_2, y_2$$$ along with the message:
"You shall find the greatest treasure of this world within a rectangle on the Cartesian plane with corners $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$." - Gol D. Roger
However, there is a slight problem with this grand declaration. The two corners given may not always designate a unique rectangle! Luffy needs you, the intern navigator, to either let him know that the clue can lead to multiple possible rectangles or the area of the rectangle that must be searched for treasure.
The first and only line of input will contain four space-separated integers $$$x_1, y_1, x_2, y_2$$$ as described above. The absolute value of all integers given as input will be at most $$$10^9$$$.
Output a single integer:
0 0 1 1
1
0 0 1 0
-1
Jack Sparrow and other pirates on The Black Pearl have been at sea for 2 months now. In order to pass the time, they have started a tournament for the gold coin game that Jack Sparrow created. The game starts with $$$x$$$ coins on the table and the goal of the game is to end up with $$$y$$$ coins on the table. There are two possible moves that a player can take. They can either remove one coin from the table or triple the number of coins on the table. Jack has decided that he wants to play in the tournament: since he created the game, he always knows the most optimal move to take and finishes the game in the least number of moves possible. Given a value for $$$x$$$ and $$$y$$$, determine the number of moves it will take Jack to complete the game.
There will be one line of input. The first integer represents $$$x$$$ $$$(1 \leq x \leq 20)$$$ and the second integer represents $$$y$$$ $$$(1 \leq y \leq 30)$$$.
Output the number of moves it will take Jack to complete the game.
5 5
0
10 24
3
For the first test case, since $$$x$$$ is already equal to $$$y$$$, Jack needs 0 moves to complete the game. For the second test case, Jack can remove 2 coins and then triple the number of coins for a total of 3 moves.
Jack Sparrow thinks that he has found the legendary Dead Man's Chest and hopes to use it to find the long-lost treasure of its owner, Davy Jones. Before he can open the chest however the ghost of Davy Jones comes and challenges Sparrow to an eccentric game to determine if he is worthy of the treasure he seeks.
Sparrow unfurls a scroll containing $$$n$$$ distinct positive integers. The game goes as follows: on each pirate's turn, they must choose a distinct $$$x$$$ and $$$y$$$ from the integers currently on the scroll such that $$$|x - y|$$$ is not on the scroll. The pirate then writes the integer $$$|x - y|$$$ on the scroll and the game continues until one of them no longer has a number they can write at which point that pirate loses and must walk the plank to eternal shame.
Davy Jones, being supremely confident, tells Sparrow that he can move first. Given the $$$n$$$ starting integers and the fact that both players play optimally, determine who will be the winner.
The first line contains an integer $$$n$$$ $$$(2 \leq n \leq 10^{4})$$$ representing the number of positive integers originally on the scroll.
The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ where for each $$$i$$$ we have $$$1 \leq a_i \leq 10^{9}$$$, representing the $$$n$$$ positive integers originally on the scroll. It is guaranteed that all $$$n$$$ numbers will be unique.
Output Jack Sparrow if Sparrow is able to win the game and thus get his treasure and Davy Jones otherwise.
2 3 9
Jack Sparrow
3 5 6 7
Davy Jones
In the first sample, Jack Sparrow is forced to choose the only two numbers there and writes the absolute value of its difference $$$6$$$ on the scroll. The scroll now has $$$\{3, 6, 9\}$$$ on it and there is no pair of elements such that the absolute difference is not already on the scroll which means that Davy Jones cannot move so Jack Sparrow wins.
The year is 1588, and you've found yourself aboard the ship of Sir Francis Drake, first Englishman to circumnavigate the globe and a government-endorsed... pirate?
Whatever the deal is, there's two things to know. Firstly, the ship has $$$n$$$ treasure rooms, labelled $$$1 \ldots N$$$, each containing a chest. The chests are also labelled $$$1 \ldots N$$$, according to their value (where chest $$$N$$$ is the most valuable). Of course, you'd like a sweet chunk of that treasure for yourself, but you and the rest of the crew have no clue which chests are in each room.
Secondly, Sir Francis Drake is also famous for helping the English defeat the Spanish Armada... which he is doing right now! In fact, it appears that you are currently in battle, and the Spanish just blew a massive hole in the side of your ship. It's only a matter of minutes before the ship completely sinks!
Of course, you don't actually care about fighting the Spanish – you, like the rest of the crew, just want to get some of the treasure before the ship goes under. Since everyone will be fighting over the most valuable chest, you decide to go after the second most valuable chest – the one labelled $$$N-1$$$.
As everyone scrambles around looking for chest $$$N$$$, you realize that you can save yourself some energy by asking them a simple question: in the rooms labelled between $$$l$$$ and $$$r$$$, what was the highest valued chest you've seen?
Quick! The ship is sinking fast, and you only have time to ask the other crewmates at most 40 questions. Can you locate the second most valuable chest before its too late?
Note that this is an interactive problem, which has different input / output format. Read below for details.
Initially, the only input will be a single integer $$$2 \leq N \leq 10^6$$$, representing the number of rooms in the ship.
The rest of the input is given through the interaction process.
For each question you want to ask to the crewmates, output "? $$$l$$$ $$$r$$$" (without quotes). After printing the query, your program should read in a single integer, which is the maximum valued treasure chest in the rooms labelled $$$l$$$ to $$$r$$$, inclusive.
After at most 40 questions, you may output "! $$$x$$$", where $$$x$$$ is the location of the second most valuable chest. Your program should exit afterwards, or else you may get unexpected verdicts. If you exceed 40 queries, you will receive Wrong Answer.
Remember to flush your output after printing each query. This can be done with fflush(stdout) in C++, System.out.flush() in Java, and stdout.flush() in Python.
5 5 4 3 2 1
? 3 5 ? 1 2 ? 2 4 ? 4 4 ? 3 3 ! 1
The sample input and output show a possible set of interactions.
In this example, the chests in rooms 1 to $$$N$$$ are 4, 3, 1, 2, 5, respectively.
You're operating a merchant ship when your second mate gives you some troubling news: you've sailed right into pirate-infested waters, headed by none other than Captain Crawfish!
The sea can be represented as an $$$N$$$ by $$$M$$$ grid with two types of characters: "." representing open water, and "#" representing land (i.e. you cannot sail on it). Your second mate has also determined the locations of all nearby pirate ships.
You are given the location of each pirate ship represented by the coordinates $$$(x_i, y_i)$$$, the direction it's facing (north, east, south, or west), and the number of locations the ship patrols, $$$k_i$$$. Pirate ships behave in the following manner:
Your ship starts in the upper left-hand corner, represented by coordinates $$$(1, 1)$$$, and you need to get to location $$$(N, M)$$$, the lower right-hand corner. In any minute, you can either move to adjacent coordinates (north, south, east, or west) or stay where you are. (Assume north is represented by the upwards direction.) You cannot move to an adjacent coordinate if it is occupied by land, and you cannot leave the bounds of the grid (legend has it the Kraken lurks beyond the bounds of the grid). If you move to a coordinate at the same time a pirate ship does, your ship is captured!
What's the minimum amount of time, in minutes, you need to traverse the waters without being captured and reach position $$$(N, M)$$$? If no path exists, output $$$-1$$$ and prepare to walk the plank!
The first line contains two integers $$$N, M, K$$$ representing the number of rows, number of columns, and the number of pirates, respectively. $$$(2 \le N \le 100, 2 \le M \le 100, 1 \le K \le 2000)$$$
The next $$$N$$$ lines contain the contents of the sea, where "." represents open water, and "#" represents land. It is guaranteed that the locations $$$(1, 1)$$$ and $$$(N, M)$$$ will have water.
The next $$$K$$$ lines describe Captain Crawfish's pirate ships: each line contains three integers $$$x_i, y_i, k_i$$$, followed by a character $$$N, S, E,$$$ or $$$W$$$, where:
Print out the minimum amount of time required to get from the upper left-hand corner $$$(1, 1)$$$ to the bottom right-hand corner $$$(N, M)$$$ without being captured. If no such path is possible, print $$$-1$$$.
5 10 2 ...####... ...####... .......... ...####... ...####... 3 3 7 E 3 4 7 E
22
5 10 2 ...####... ...####... .......... ...####... ...####... 3 3 6 E 3 4 6 E
-1
For the sake of simplicity, assume all ships move instantaneously. That is, you will be captured if and only if you move to some location at the same time as a pirate ship, regardless of where you or the pirate ship came from.
Multiple pirate ships can coexist in the same location.