Battleship is a game in which one player tries to guess the location of his opponent's ships.
For example, suppose your board looks like this:
0 1 2 3 4
0 O O O S O
1 O S O S O
2 O O O O O
3 S S O O O
4 O S O O O
where O represents a tile of the ocean and S represents a ship.
If your opponent guesses $$$(3,1)$$$, representing the tile in row 3 and column 1, they would hit a ship.
If your opponent guesses $$$(4,4)$$$, representing the tile in row 4 and column 4, they would miss and hit the ocean.
Given the state of an $$$n\times n$$$ board and the coordinates your opponent guesses, return "No" if your opponent hits a ship and "Yes" if your opponent misses.
The first line contains three integers $$$n,r,c$$$ $$$(1\le n\le 100,0\le r,c \lt n)$$$, indicating the size of the board and the coordinates $$$(r,c)$$$ your opponent guesses.
The next $$$n$$$ lines each contain $$$n$$$ characters, O or S, indicating whether the position is the ocean or a ship.
Print "No" if your opponent hits a ship and "Yes" otherwise.
5 3 1 O O O S O O S O S O O O O O O S S O O O O S O O O
No
I would've won this game if my knight can move diagonally like a bishop!
Yifan created an imaginary piece, knishop, in order to win in a chess tournament. It can move like a knight or a bishop in all moves. More formally, if a knishop is currently at coordinate $$$(x,y)$$$:
In Yifan's imagination, a chessboard is a cartesian plane without a boundary. In other words, pieces can move to any point with integer coordinates, like $$$(-1,-2)$$$. To test the power of this piece, Yifan wants to move his knishop from $$$(x_1,y_1)$$$ to $$$(x_2,y_2)$$$ in the minimum number of moves. Find the minimum number of moves needed.
The first line contains 4 integers $$$x_1,y_1,x_2,y_2$$$ $$$(-10^9\le x_1,y_1,x_2,y_2\le 10^9)$$$.
The minimum number of moves needed.
0 0 1 2
1
1 1 -100 -100
1
In the first example, the knishop moves like a knight.
In the second example, the knishop moves diagonally, like a bishop.
When Gunga was 3 years old, he got extremely interested in both math and coding. One day, he found a bashy number theory problem when he was preparing for a math competition, and he decided to solve it by programming. The problem can be generalized as follows:
Given an array with $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$, find the number of ordered pairs $$$(i,j)$$$ such that $$$1\le i,j\le n,i\neq j$$$ and $$$a_i$$$ is a multiple of $$$a_j$$$.
The first line contains an integer $$$n$$$ $$$(1\le n\le 2\times10^5)$$$ - the number of elements in the array.
The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ $$$(1\le a_i\le 5\times10^5)$$$ - elements of the array $$$a$$$.
Print a single integer - the number of ordered pairs that satisfied the constraints.
5 1 2 3 4 5
5
In the first example, there are $$$5$$$ pairs, $$$(2,1),(3,1),(4,1),(5,1)$$$, and $$$(4,2)$$$.
Rectangular Star Trek posters are hanging on Michael's wall. His goal is to one day cover the entire wall, but he's unsuccessful so far. Fortunately, he has enough pieces of tape to move one of his posters to a new location.
Given the location of his existing posters, return "Yes" if it's possible for Michael to cover the entire wall by moving one poster and "No" otherwise.
For example, his wall may look like this:
1 2 3 4 5
1 1 1 0 0 0
2 1 1 0 0 0
3 0 0 0 0 0
4 0 0 1 1 1
5 0 0 1 1 1
with the coordinates of the posters being (1, 1) and (2, 2) for the first and (4,3) and (5,5) for the second.
The first line contains a single integer $$$N$$$ $$$(1\le N\le 10)$$$ - the number of posters.
For the following $$$N$$$ lines, each line contains 4 integers $$$x_1,y_1,x_2,y_2$$$ $$$(1\le x_1,y_1,x_2,y_2\le 20)$$$ describing $$$(x_1,y_1)$$$, the upper left corner, and $$$(x_2,y_2)$$$, the lower right corner, of the $$$i$$$-th posters.
Print "Yes" if it's possible for Michael to cover the entire wall by moving one poster and "No" otherwise. (without quotes)
Gunga changes his computer's password once a week, and he has a list of $$$n+1$$$ different passwords. In week 1, he has the first password in his list as his password. At the beginning of every week, he changes his password. He chooses $$$1$$$ out of the other $$$n$$$ passwords randomly to be his new password. However, there's $$$\frac{1}{m}$$$ chance that he forgets changing it each week. More formally, there is $$$\frac{1}{m}$$$ chance of not changing the password and $$$\frac{m-1}{m}$$$ chance of changing it to a different one chosen by random.
Unfortunately, at the end of the $$$T$$$-th week, careless Gunga forgot his password again! If the maximum possible number of attempts for Gunga is $$$k$$$ and he is trying all the possible passwords in the list's order, what is the probability that he can open his computer?
In other words, what is the probability that he uses one of the first $$$k$$$ passwords on his list in the $$$T$$$-th week? Assume that the answer is a reduced fraction of the form $$$\frac{x}{y}$$$ ($$$\gcd(x, y)=1$$$), output integer $$$z$$$ such that $$$zy\equiv x \pmod{10^9+7}$$$. In other words, output $$$x y^{-1} \pmod{10^9+7}$$$.
A single line containing 4 integers $$$n,m,k,T$$$ $$$(1\le n,m,k\le 10^9,1\le T\le 10^5)$$$.
Assume that the answer is a reduced fraction $$$\frac{x}{y}$$$, output $$$xy^{-1}\pmod{10^9+7}$$$.
3 2 3 4
92592594
100 37 53 4568
490435543
In the first example, let $$$P_1,P_2,P_3,P_4$$$ denote the probability of using the $$$i$$$-th password.
On the first week, Gunga is using the 1st password.
On the second week, $$$P_1=\frac12,P_2=P_3=P_4=\frac16$$$.
On the third week, $$$P_1=\frac13,P_2=P_3=P_4=\frac29$$$.
On the fourth week, $$$P_1=\frac{5}{18},P_2=P_3=P_4=\frac{13}{54}$$$.
The answer is
$$$$$$\frac{5}{18}+\frac{13}{54}+\frac{13}{54}=\frac{41}{54}$$$$$$ Thus $$$x=41, y=54$$$.
We should output $$$41\cdot 54^{-1} \pmod{10^9+7} = 92592594$$$
If you are not familiar with getting $$$x^{-1}$$$ under modular arithmetic, Yifan has prepared a code for you in c++! (For people with different coding languages, try using the code as a reference and come up with your own!)
https://pastebin.com/SuD839YA
You are given an array $$$a$$$ of length $$$n$$$. Find the number of ordered pairs $$$(x,y,z)$$$ such that $$$a_x\times a_y = a_z$$$ .
The first line contains an integer $$$n$$$ $$$(1\le n\le100)$$$- the number of elements in the array.
The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ $$$(1\le a_i\le 10^4)$$$ - elements of the array $$$a$$$.
Print a single integer - the number of ordered pairs that satisfied the constraints.
9 1 1 2 2 3 3 4 4 5
68
Gunga is trying to escape Michael. Initially, he starts at position $$$1$$$. In front of him, there are a series of platforms on which he can stand. Some of the platforms are on the ceiling, others on the floor. He cannot stand on empty space (and will fall and die if he does). While running, he can turn on and off his anti-gravity boots which instantaneously flip his orientation, allowing him to walk on the ceiling platforms. His anti-gravity boots can be activated as much as Gunga wants.
Note: the anti-gravity boots will flip Gunga, but during this period Gunga will not move forward any blocks.
Given the starting position and length of each platform on the ceiling and the floor, determine the farthest position Gunga can reach.
The first line contains two single integers $$$n,m$$$ $$$(1\le n,m\le 10^5)$$$ - the number of platforms on the floor and on the ceiling.
The next $$$n$$$ lines contain two integers $$$a_i,b_i$$$ $$$(1\le a_i,b_i\le 10^9)$$$ - the starting position of the $$$i$$$-th platform and its length, which means that it spans the segment $$$[a_i,a_i+b_i-1]$$$.
The next $$$m$$$ lines contain two integers $$$c_i,d_i$$$ $$$(1\le c_i,d_i\le 10^9)$$$ - the starting position of the $$$i$$$-th platform and its length, which means that it spans the segment $$$[c_i,c_i+d_i-1]$$$ on the ceiling.
It's guaranteed that no two floor platforms overlap. Similarly, no two ceiling platforms overlap.
A single line containing the farthest position Gunga can reach.
2 3 4 2 1 2 5 10 2 3 100 5
14
In the first example, Gunga can move to position 2 on the platform on the floor, then switch to the ceiling and move to position 4. Then switch back to the floor and move to position 5. Finally, he can switch to the ceiling again and move to position 14.
Michael is grocery shopping and must give the cashier at least $$$N$$$ $$$(1\le N\le 10^9)$$$ dollars (if he exceeds his total, his cashier will simply give him the appropriate amount of change). However, Michael does not like the digits 2 and 7, so he does not want to pay an amount wherein any digits are multiples by 2 or 7 (notice that 0 is a multiple of any number!). Find the smallest number where this is possible.
The first line contains an integer $$$N$$$, the minimum amount of dollars Michael will pay.
A single line containing the smallest number that satisfies the constraint.
2
3
70
91
777777777
911111111
Gunga have a permutation $$$p_1,p_2,\dots,p_n$$$ of length $$$n$$$ . He generates a sequence $$$a_1,a_2,\dots,a_n$$$ such that $$$a_i$$$ is either the minimum or the maximum number among $$$p_1,p_2,\dots,p_n$$$ . Given the sequence $$$a_1,a_2,\dots,a_n$$$ , can you recover the original permutation?
The first line contains a single integer $$$n$$$ $$$(1\le n\le1000)$$$. The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ $$$(1\le p_i\le n)$$$.
If there is a possible solution for the permutation, print "YES", otherwise print "NO". (without quotes)
5 2 2 3 1 5
YES
5 1 1 1 1 2
NO
In the first example, a possible permutation will be $$$2,3,1,4,5$$$.
In the second example, no possible permutation exists.
Two players with 6900 trophies can beat the best player in the world!
Recently, the game "Rash Cloyale" went viral on campus and people started challenging others in its unique 2v2 mode. Each player has a rating, and a team will win the 2v2 game if the sum of their ratings is higher than their opponents. (We define the team's rating as the sum of the ratings of its players.)
There are $$$2n$$$ players on campus ready for a friendly battle! To make the tournament relatively interesting to watch, the organizers decide to separate the players into 2 groups with $$$n$$$ people, A and B. Then each player from group A will form a team with a player from group B.
The team, or teams, with the highest rating will win the entire tournament. Of all possible teams that could be made, what's the minimum rating needed to win the tournament? That is, amongst all different ways to match all the teams, what is the minimum rating of the winner of the tournament?
The first line contains a single integer $$$n$$$ $$$(1\le n\le 10^5)$$$ - the number of people in a single group.
The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ $$$(1\le a_i\le 10^9)$$$ - the ratings of people in group A.
The third line contains $$$n$$$ integers $$$b_1,b_2,\dots,b_n$$$ $$$(1\le b_i\le 10^9)$$$ - the ratings of people in group B.
Print the lowest possible rating of the winning team.
2 1 10 1 10
11
In the first example, we can pair up $$$(a_1,b_1),(a_2,b_2)$$$, then the maximum sum of the ratings is $$$a_2+b_2=20$$$. However, we can also pair up $$$(a_1,b_2),(a_2,b_1)$$$, then the maximum sum of the ratings is $$$a_1+b_2=a_2+b_1=11$$$.
Yifan remembered a game that he used to play as a kid - hopscotch. The game is made of two rows of $$$n$$$ squares $$$(1\le n\le300)$$$. The $$$i$$$-th square on the left is assigned with an integer value $$$a_i$$$ $$$(-10^4\le a_i\le 10^4)$$$ and the $$$i$$$-th square on the right is assigned with value $$$b_i$$$ $$$(-10^4\le b_i\le 10^4)$$$. The player starts with the left foot on $$$a_1$$$ and the right foot on $$$b_1$$$ and must eventually ends on $$$a_n$$$ and $$$b_n$$$.
The game continues by making steps: In each step, the player can pick one foot and move forward in the same row. The goal of his game is to maximize the sum of the values of all the scores he steps on. You may take multiple steps on the same foot.
After recalling the rules of the game, Yifan challenges Michael to it. Due to physical limitations, Michael's feet cannot be over $$$K$$$ $$$(1\le K\le n)$$$ squares away from each other. More formally, if the left foot is on $$$a_i$$$ and the right foot is on $$$b_j$$$, $$$|i-j|\le K$$$ must hold. However, Michael still wants to win the game to demonstrate his brilliance. What's the maximum score Michael can get?
The first line contains two integers $$$n,K$$$ $$$(1\le K\le n\le300)$$$- the number of elements in the array.
The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ $$$(-10^4\le a_i\le 10^4)$$$ - the values of squares on the left.
The second line contains $$$n$$$ integers $$$b_1,b_2,\dots,b_n$$$ $$$(-10^4\le a_i\le 10^4)$$$ - the values of squares on the right.
Print the answer - the maximum score Michael can get.
4 1 0 2 2 8 0 -10 5 2
19
7 2 0 -10 -6 2 -10 0 0 5 3 -2 -1 -10 -10 0
9
In the first case 1, your score is $$$0 + 2 + 2 + 8 + 0 + 5 + 2 = 19$$$.
In the second case 2, your score is $$$0 + 2 + 0 + 0 + 5 + 3 + -1 + 0 = 9$$$.
Michael needs to walk to school every day from downtown. There're $$$n$$$ crossings and $$$m$$$ paths connecting these crossings. Michael starts by crossing $$$1$$$ he needs to reach crossing $$$T$$$. Now, because of the fabulous New England weather, each path $$$i$$$ is either covered in snow with depth $$$x_i$$$ or cleared of snow by the hard-working oppressed lower class. Walking in snow is tiring, so walking along each snowy path increases Michael's dreariness $$$d$$$ by $$$1$$$. Further, walking on snow costs Michael energy. The energy of crossing the path $$$i$$$ is $$$d \times x_i$$$. Find the minimum energy Michael needs to get to school.
The first line contains 3 integers $$$n,m,T$$$ $$$(1\le n\le 1000,1\le m\le \min(1000,\frac13 n^2), 1\le T\le n)$$$. The following $$$m$$$ lines each contains 3 integers $$$a_i,b_i,x_i$$$ $$$(1\le a_i,b_i\le n,0\le x_i\le 100)$$$.
Print the minimum energy Michael needs to get to school. Output -1 if he cannot.
4 4 4 1 2 43 2 4 74 1 3 78 3 4 98
74
5 1 1 3 4 14
0
There are $$$n$$$ people standing in a line for the best dish at Andover - beef teriyaki. Knowing that people like to stick with their friends while waiting for food, Arnav observes that the $$$i$$$-th person in the line knows the $$$j$$$-th person if and only if $$$i-a_i\le j\le i + b_i$$$. If two people know each other, we say they are friends. How many pairs of friends are there in the line?
The first line contains two integers $$$n$$$ $$$(1\le K\le n\le5\times10^5)$$$- the number of people in the line.
The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ $$$(1\le a_i\le n)$$$ - the elements of the array $$$a$$$.
The second line contains $$$n$$$ integers $$$b_1,b_2,\dots,b_n$$$ $$$(1\le a_i\le n)$$$ - the elements of the array $$$b$$$.
Print the answer - the number of friends in the line.
3 3 3 3 3 3 3
3
5 0 1 2 0 1 2 1 0 0 1
3
In the first example, there are 3 pair of friends, $$$(1,2),(1,3)$$$, and $$$(2,3)$$$.
In the second example, there are also 3 pair of friends, $$$(1,2),(1,3)$$$, and $$$(2,3)$$$.
Yifan remembered a game that he used to play as a kid - hopscotch. The game is made of two rows of $$$n$$$ squares $$$(1\le n\le10^5)$$$. The $$$i$$$-th square on the left is assigned with an integer value $$$a_i$$$ $$$(-10^4\le a_i\le 10^4)$$$ and the $$$i$$$-th square on the right is assigned with value $$$b_i$$$ $$$(-10^4\le b_i\le 10^4)$$$. The player starts with the left foot on $$$a_1$$$ and the right foot on $$$b_1$$$ and must eventually ends on $$$a_n$$$ and $$$b_n$$$.
The game continues by making steps: In each step, the player can pick one foot and move forward in the same row. The goal of his game is to maximize the sum of the values of all the scores he steps on. You may take multiple steps on the same foot.
After recalling the rules of the game, Yifan challenges Michael to it. Due to physical limitations, Michael's feet cannot be over $$$K$$$ $$$(1\le K\le n)$$$ squares away from each other. More formally, if the left foot is on $$$a_i$$$ and the right foot is on $$$b_j$$$, $$$|i-j|\le K$$$ must hold. However, Michael still wants to win the game to demonstrate his brilliance. What's the maximum score Michael can get?
The first line contains two integers $$$n,K$$$ $$$(1\le K\le n\le5\times10^5)$$$- the number of elements in the array.
The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ $$$(-10^4\le a_i\le 10^4)$$$ - the values of squares on the left.
The second line contains $$$n$$$ integers $$$b_1,b_2,\dots,b_n$$$ $$$(-10^4\le a_i\le 10^4)$$$ - the values of squares on the right.
Print the answer - the maximum score Michael can get.
4 1 0 2 2 8 0 -10 5 2
19
7 2 0 -10 -6 2 -10 0 0 5 3 -2 -1 -10 -10 0
9
In the first case 1, your score is $$$0 + 2 + 2 + 8 + 0 + 5 + 2 = 19$$$.
In the second case 2, your score is $$$0 + 2 + 0 + 0 + 5 + 3 + -1 + 0 = 9$$$.