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:
- If the clue could designate multiple possible rectangles, output $$$-1$$$.
- Otherwise, output the area of the unique rectangle where the One Piece is hidden.
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:
- Each pirate ship starts in the given position.
- At each minute, each pirate ship moves one unit in the direction it is facing. It is guaranteed that this move is possible, that is, it is in bounds and is not occupied by land.
- When the pirate ship has moved exactly $$$k_i - 1$$$ times, meaning it has patrolled its designated $$$k_i$$$ locations, it turns 180 degrees. (The turn takes no time).
- The pirate ship follows the same process in the reverse direction, traveling one unit every minute.
- When the pirate ship reaches its starting location, it once again turns 180 degrees, taking no time, and repeats the process.
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:
- $$$(x_i, y_i)$$$ is the starting location of the pirate ship. $$$(1 \le x_i \le N, 1 \le y_i \le M)$$$. No pirate ship will start at location $$$(1, 1)$$$.
- $$$k_i$$$ represents the number of locations the pirate ship patrols. $$$(1 \le k_i \le 8)$$$
- The character represents the direction the pirate ship faces initially. (N-north, S-south, E-east, W-west).
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.
Veos the treasure hunter has a quest for you! He has given you an arithmetic progression. Namely, it is denoted by the integers $$$a$$$ and $$$b$$$, with the arithmetic progression taking on the form $$$a, a + b, a + 2b, a + 3b, \dots$$$ and so on, with the first element in the progression being $$$a$$$.
Veos tells you that hidden within the arithmetic progression is a treasure and thus you must investigate a property of the arithmetic progression you've received. Notably, you want to find a contiguous subsequence of $$$k$$$ "clue"s in the arithmetic progression. Here, a "clue" is defined to be an element of the arithmetic sequence which is composite.
More formally, you would like to find an integer $$$x$$$ such that the numbers $$$a + xb, a + (x + 1)b, a + (x + 2)b, \dots, a + (x + k - 1)b$$$ are all composite.
Veos tells you that, "X marks the spot!", meaning that finding a suitable value for $$$x$$$ will lead you directly to the treasure! Are you up to the challenge?
The input will consist of a single line containing the space-separated integers $$$a, b\ (3 \leq a, b \leq 100,000), k\ (1 \leq k \leq 1,000)$$$ in that order.
The output should consist of a single integer, a suitable value of $$$x$$$. If there are multiple such values for $$$x$$$, output any of them.
4 3 1
2
3 5 2
5
A composite number is a natural number which can be factored into at least two smaller natural numbers. Some examples of composite numbers are $$$6$$$ ($$$2 \cdot 3 = 6$$$) and $$$100$$$ ($$$4 \cdot 25 = 100$$$).
A contiguous subsequence is a subsequence in which elements can be arranged in a consecutive fashion.
Redbeard, the leader of the great Red Pearl pirate ship, is trying to test his crew. His crew consists of $$$n$$$ pirates and he has prepared a set of $$$m$$$ trials for his crew.
However these trials have not taken place yet. Redbeard would love for the results to satisfy a few properties. One, each pirate should pass at least one trial, otherwise they would be too sad. Two, no pirate should complete all of the trials successfully, otherwise they would be too confident. And three, every trial should be completed by at least one crew member. In how many ways can the results of the trials occur such that all three of these properties hold? Results are considered distinct if some crew member has a different outcome on some trial.
Can you determine how many ways trials can result modulo $$$10^9 + 7$$$?
The first line of input contains two space-separated integers $$$n$$$ ($$$1 \leq n \leq 1000$$$) and $$$m$$$ ($$$1 \leq m \leq 10$$$).
Output a single integer which represents the number of possible results satisfying Redbeard's desired properties modulo $$$10^9 + 7$$$.
2 2
2
4 2
14
Edward Kenway, the most fearsome pirate-assassin ever to sail the seven seas, has stumbled upon a massive amount of buried treasure. He decides to split the treasure among his $$$n$$$ crewmates by running a race and giving rewards based on the race placements.
However, some crewmates realize that they can stand to gain more by forming coalitions and splitting the rewards among all members of a coalition (as bigger coalitions are more likely to have higher placing members).
Edward decides to have his crewmates run a race, take the highest ranking crewmate in each coalation, rank the coalitions in terms of each coalition's highest ranking crewmate, and give every crewmate in the coalition the rank of their coalition. Each crewmate is equally fast, so every single permutation of crewmate race placements is equally likely.
Given this information and the crew members in each of the $$$k$$$ coalitions, output the expected rank of each crew member given Edward Kenway's scheme. Each crew member's expected rank can be expressed as a rational $$$\frac{p}{q}$$$. Output $$$pq^{-1} \pmod {10^9 + 7}$$$ for each crew member.
The first line consists of two integers $$$n, k$$$ $$$(1 \leq k \leq n \leq 250)$$$, giving the number of crewmates and number of coalitions.
The next $$$k$$$ lines each consist of a single integer $$$s_i$$$, giving the size of the $$$i$$$th coalition and the next $$$s_i$$$ integers in the line give all crewmates in that coalition. Every crewmate is guaranteed to be in a coalition.
Output $$$n$$$ integers, where the $$$i$$$th integer is the expected rank of the $$$i$$$th crewmate.
5 1 5 1 2 3 4 5
1 1 1 1 1
5 2 3 1 2 3 2 4 5
800000007 800000007 800000007 200000003 200000003
In the first sample, every single crewmate belongs to the same coalition, so each crewmate will always be rank $$$1$$$.
In the second sample, there is a $$$\frac{3}{5}$$$ chance that the first coalition is rank $$$1$$$ and a $$$\frac{2}{5}$$$ chance that the second coalition is rank $$$1$$$. All crewmates in the first coalition have an expected rank of $$$1 \cdot \frac{3}{5} + 2 \cdot \frac{2}{5} = \frac{7}{5}$$$ and all crewmates in the second coalition have an expected rank of $$$1 \cdot \frac{2}{5} + 2 \cdot \frac{3}{5} = \frac{8}{5}$$$.