The first game to play is red light green light. Each player is allowed to move while there is a green light but most stop and stay in place while there is a red light. There are $$$N$$$ participants in the game and you know when exactly what times the light is going to change. Given this, you've been tasked with figuring out which participants will be able to reach the finish line before the light turns red forever (i.e. there are no more times at which the line changes).
The light starts at red and all players can accelerate and decelerate instantly.
The first line has three integers, $$$M$$$, $$$N$$$, and $$$K$$$. $$$1 \leq M \leq 5000$$$ is the number of light changes, $$$1 \leq N \leq 5000$$$ is the number of participants, and $$$1 \leq K \leq 10000$$$ is the distance the end is from the start in meters.
The next line contains $$$M$$$ integers $$$1 \leq t_i \leq 5000$$$, when the changes happen from red to green (or vice-versa) in seconds since the beginning. ($$$M$$$ will be an even number so that at the end the light will be red)
The next line contains $$$N$$$ integers, the speed of a participant $$$1 \leq p_i \leq 10$$$ in meters per second.
The output should be one line with $$$N$$$ space-separated integers. The $$$i$$$th integer should be $$$0$$$ if the $$$i$$$th competitor will lose and $$$1$$$ if the $$$i$$$th competitor will win.
4 3 10 4 2 7 5 4 2 3
1 0 1
2 1 1000 1 500 2
0
You are attempting to build an optimal team for the upcoming game: Tug of War! To give yourself the best chance of winning, you decide to select the optimal team of size $$$\frac{n}{2}$$$ of a pool of $$$n$$$ contestants (for even $$$n$$$), where the optimal team is the team that gives the highest probability of winning against the opposite team made from the leftover contestants not on the chosen team. Furthermore, you want to estimate the probability that you actually win against the team made from the opposite team.
Each of the $$$n$$$ contestants have a strength rating, $$$s_i$$$, and the strength rating of a team is the sum of the strength ratings of all the members of the team. To calculate the probability of a team with strength rating $$$a$$$ of beating a team with strength rating $$$b$$$, you decide to use the standard ELO formula, which is given below.
$$$$$$ \frac{1}{1 + 10^{\frac{b - a}{400}}} $$$$$$
Given this information, output the strength rating of your optimal team and the probability this team beats the team of leftover contestants!
The first line consists of a single even integer $$$n$$$ $$$(2 \leq n \leq 100)$$$, which gives the number of contestants. The next line consists of $$$n$$$ integers $$$s_i$$$ $$$(1 \leq s_i \leq 100)$$$, which gives the strength rating of each contestants.
Output the strength rating of the optimal team and the probability that that optimal team beats the team made of the unpicked contestants.
6 4 5 2 1 3 6
15 0.5129491448928637
The remaining contestants hear that they must play ppopgi but the game has a new twist. Rather than having a contestant extract a stamped shape from the honeycomb, they must instead play the following game:
Each player is randomly paired with another player. They are given a large, rectangular honeycomb with a length of $$$x$$$ centimeters and width $$$y$$$ centimeters. Then, the players must alternate cutting circles of radius $$$r$$$ centimeters out from the rectangle where the new circle being cut out must be whole (i.e. you cannot cut a circle that overlaps - though it is allowed to be tangential to - another already cut-out circle or does not fit within the rectangle). Each player may choose any part of the rectangle to cut the circle out of as long as they can still cut out a circle of radius $$$r$$$ centimeters as described above. A player loses when they are no longer able to cut out a circle of the desired size.
Players 067 and 199 are drawn to play against each other with player 199 getting to go first. Given that both players' lives are on the line, they both play optimally. Player 001 is watching from the outside and wants you to figure out who will win the game.
The input is three space-separated integers $$$x, y, r$$$ where $$$x$$$ and $$$y$$$ are the length and width of the honeycomb in centimeters and $$$r$$$ is the radius of the desired circle in centimeters ($$$1 \leq x, y, r \leq 1000$$$).
Output the ID of the player who wins if both play optimally and player 199 goes first (output 199 if player 199 wins and 067 if player 067 wins).
7 7 3
199
6 5 4
067
In the first test case, there is only room to cut out one circle so player 199 wins.
Ali is preparing for a new game, involving a complex maze filled with dangerous hazards. Luckily, Ali has access to useful intel in the form of a map of the maze, telling him which of the of the four directions (up ^, down v, left <, or right >) he should move in given the current location to avoid a hazard. Additionally, some locations in the maze are marked O on the map as rescue points, where if a contestant can make it there, she will be safely extracted from the treacherous game.
Help Ali evaluate his odds of safely escaping the maze! Count the number of locations in the maze where if Ali starts at that location and follows the directions on his secret map, he will make it safely to a rescue point.
The first line of input contains two space-separated integers $$$R$$$ and $$$C$$$ ($$$1\leq R, C \leq 10^3$$$), denoting the number of rows and columns in the maze respectively. $$$R$$$ lines follow, each containing $$$C$$$ characters where each character will be one of five possibilities: < to indicate that Ali should move left, > to indicate that he should move right, ^ for him to move up, and v for him to move down in the maze. Lastly, O denotes a rescue point where Ali could make it out alive if he got there.
Print the number of locations in the maze where if Ali started there, he could be certain to make it to a rescue point. Note, Ali could start out at any location in the maze, including at a rescue point.
3 7 >>v>>>v O<<^v^< ^><v>O^
10
Player 101 and player 278 are playing a game to decide who advances to the next round. Due to the massive stakes player 101 decides to rig the game in his favor.
The game goes as follows. There is a start location and a straight-line path of length $$$t$$$ miles to the finish line. Player 101 must take a single red marble from the start line to the finish line before player 278 catches him.
When the whistle blows to start running, player 278 is required to wait $$$d$$$ hours before beginning to chase after player 101. Player 101 runs at $$$a$$$ miles per hour while player 278 runs at $$$b$$$ miles per hour. However, the twist in the game is that player 101 tricks player 278 into believing that there is an additional rule such that whenever you find a blue marble, you must take it back to the start line and wait $$$s$$$ hours before beginning running again.
Player 101 bribes a guard to get some blue marbles and decides to drop a blue marble each time player 278 catches up to him (which means that player 278 must go all the way back to the start line, wait $$$s$$$ hours, and then resume his chase). If player 101 doesn't have a blue marble when player 278 catches up to him then player 101 loses. If player 101 and player 278 both reach the finish line at the same time, player 101 wins and he does not need a blue marble in that case.
Player 101 needs to pay for each blue marble he gets from the guard so he asks you what is the smallest number of blue marbles he needs to buy so that he can get to the finish line (assume he runs the whole time without stopping, dropping the marble takes negligible time) without losing the game.
The single line of input contains $$$5$$$ space separated-integers $$$a, b, t, d, s$$$ where $$$a$$$ is the speed of player 101 in miles per hour, $$$b$$$ is the speed of player player 278 in miles per hour, $$$t$$$ is how many miles away the finish line is, $$$d$$$ is how many hours player 278 must wait before chasing, and $$$s$$$ is how long player 278 must wait at the start line after bringing back a blue marble. ($$$1 \leq a, b \leq 100$$$, $$$1 \leq t \leq 10^{4}$$$, and $$$1 \leq d, s \leq 10$$$)
A single integer representing the minimum number of blue marbles player 101 must buy in order to guarantee him victory.
1 2 9 1 1
2
3 10 100 4 2
3
In the first example, player 278 waits for an hour at which point player 101 is $$$1$$$ mile away. Player 278 then catches up at the $$$2$$$-mile mark at which point player 101 drops one blue marble. It will take $$$1$$$ hour for player 278 to get back to the start line and then he must wait for $$$1$$$ more hour at which point player 101 will be $$$4$$$ miles away. Player 278 then catches up to player 101 at the $$$8$$$-mile mark and so player 101 drops another blue marble at which point he then has enough time to get to the finish line without player 278 catching up again which is why he needs $$$2$$$ blue marbles to guarantee a win.
Once again, Ali knows that the next game he must face in Squid Game will be a dangerous maze, riddled with perils at every turn. He has another map of the maze, providing intel on how to move in each location to avoid hazards. However, this time there aren't any rescue points inside the maze–contestants must completely leave the maze grid in order to reach safety.
Ali knows that if he isn't careful when trying to navigate the maze, he might be too busy avoiding hazards to actually escape. Specifically, if all Ali does is follow the direction instructions at each location, he might find himself in an infinite loop that will never escape the maze. Because of this issue, Ali wants to know the number of unordered pairs of distinct locations in the maze such that both locations are reachable if Ali starts at the opposite location in the pair and follows the intel. Can you write a program to calculate the answer?
The first line consists of two integers $$$R$$$ and $$$C$$$ $$$(1 \leq R, C \leq 300)$$$, which give the number of rows and columns of the maze.
The next $$$R$$$ lines consist of $$$C$$$ characters which are all either $$$\texttt{^}, \texttt{v}, \texttt{ \lt }, \texttt{ \gt }$$$ and represent the directions Ali should move in each location to avoid hazards (up, down, left, and right, respectively). The $$$j$$$th character in the $$$i$$$th line gives the direction Ali should move when in row $$$i$$$ and column $$$j$$$ of the maze.
Output a single integer giving the number of unordered pairs of locations $$$(a, b)$$$ such that $$$a \neq b$$$, Ali will eventually reach $$$a$$$ starting at location $$$b$$$, and Ali will eventually reach $$$b$$$ starting at location $$$a$$$.
2 2 >v ^<
6
2 2 >v ^^
1
In the first test case, all points are reachable starting from any point, so all $$$6$$$ unordered pairs of distinct locations are valid.
In the second test case, the only valid pair is the first row and second column and the second row and second column.
The organizers of Squid Game have added a new task. In this task, the contestants find themselves lost in a strange maze. Please help them answer some questions and better understand their predicament.
In this maze, there are $$$N$$$ different rooms numbered $$$1...N$$$, linked by doors in such a way that all rooms are connected and only $$$N - 1$$$ doors exist (connecting exactly two rooms each). The Squid Game organizers are in the main room, room $$$1$$$, and are kind enough to volunteer to bring back contestants if they get close enough to the main room.
There are $$$Q$$$ contestants. Each contestant $$$i$$$ finds themselves in a room $$$r_i$$$ and are told they will be rescued immediately if they are within $$$d_i$$$ of room $$$1$$$. For each contestant, please determine the room in which they will be rescued.
The first line contains two integers: $$$1 \leq N, Q \leq 100,000$$$
The next $$$N-1$$$ lines describe the doors with the $$$i$$$th line containing two space-separated integers $$$u_i$$$ and $$$v_{i}$$$, linking the two specified rooms ($$$1 \leq u_i, v_i \leq N$$$). Each pair of rooms that are connected will be listed exactly.
The last $$$Q$$$ lines describe each contestant, providing the values $$$r_i$$$ ($$$1 \leq r_i \leq N$$$) and $$$d_i$$$ ($$$0 \leq d_i \leq N$$$) representing the starting room and the distance that the participant must be within from room $$$1$$$ to be rescued.
Each line describes the room in which the corresponding contestant will be rescued.
7 4 1 2 2 7 1 3 4 3 4 5 4 6 5 1 6 2 2 0 7 2
3 4 1 7
A contestant may begin within $$$d_i$$$ of room $$$1$$$.
The Front Man needs your help for generating dalgona patterns for the contestants of the upcoming 2022 Crab Games! However, he wants to modify the game to have players walk on top of a field to trace out the designated pattern. Each player is given a field that can be described as a Cartesian plane consisting of all coordinates $$$(x, y)$$$ such that $$$-N \leq x, y \leq N$$$. A player starts facing rightward at $$$(0, 0)$$$ and takes a step $$$1$$$ unit forward. For every subsequent move, they either take a step $$$1$$$ unit forward, or turn $$$90$$$ degrees counterclockwise before taking a step $$$1$$$ unit forward. The player repeats these actions until reaching the point $$$(N, N)$$$ or being disqualified by the overseeing doll. Disqualification occurs if a contestant goes on the same point twice or moves outside the designated area on the plane. An admissible pattern is a sequence of moves that can be traced by the players without being disqualified and ends in the player ceasing to move. Below is an example of such a pattern when $$$N = 2$$$.
There are many possible walks that can be completed by a player, but the Front Man would like to know the maximum number of distinct puzzles he could offer to contestants given $$$N$$$.
The first and only line of input contains a single positive integer $$$N$$$ ($$$1 \leq N \leq 100000$$$) as described above.
Print one number representing the number of possible dalgona patterns the Front Man can create modulo $$$10^9+7$$$.
1
1
2
9
3
82
Player 278 is upset about Player 101's treachery in their previous game of marbles and asks the Front Man for another chance to beat Player 101 in a marble game. The Front Man, upset about one of his guards ruining the sanctity of the game by colluding with Player 101, grants the request and lets player 278 pick the new game.
Player 101 starts with $$$n$$$ marbles. Due to player 278's expertise in the new game, for every integer $$$t$$$, if player 101 has $$$m$$$ marbles at the end of round $$$t$$$, then during round $$$t + 1$$$, for each of the $$$m$$$ marbles, player 278 has a probability of $$$p$$$ of taking it from player 101.
Given this, the Front Man wants to know the expected number of rounds it will take for player 278 to take all of player 101's $$$n$$$ marbles. This number can be expressed as some rational $$$\frac{p}{q}$$$. Output $$$pq^{-1} \pmod {10^9 + 7}$$$.
The input is a single line containing two space-separated integers $$$n$$$ and $$$p$$$ ($$$1 \leq n \leq 500$$$ and $$$1 \leq p \leq 100$$$) where $$$n$$$ is the number of marbles that player 101 starts with and $$$p$$$ is the probability of taking a marble.
The expected number of rounds (modulo $$$10^{9} + 7$$$) it will take for player 278 to take all of player 101's $$$n$$$ marbles.
2 100
1
1 50
2
5 33
737005287