Not many know that after the events of the popular fairy tale, Goldilocks took up a job as the official porridge chef for the bear family to pay for her Deepseek subscription. Business was simple at first, but the bear family has grown quite large, and their breakfast demands are getting out of hand.
To make things easier, they've given Goldilocks a list of the temperature ranges each bear finds just right. Now, Goldilocks is wondering how many bears she could satisfy by preparing porridge at some specific temperatures. Help her answer these queries!
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 10^5$$$) — the number of bears and the number of temperature queries.
The next $$$n$$$ lines contain two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq 10^9$$$), representing the temperature range $$$[l_i, r_i]$$$ that the $$$i$$$-th bear finds acceptable (note that this range is inclusive).
The next $$$q$$$ lines each contain a single integer $$$t_i$$$ ($$$1 \leq t_i \leq 10^9$$$) — a porridge temperature for which Goldilocks wants to know how many bears will be satisfied.
For each query temperature $$$t_i$$$, output a single integer on a new line — the number of bears that will be satisfied with porridge at that temperature.
2 31 55 105611
2 1 0
At temperature $$$5$$$, both bears are satisfied — $$$5$$$ is in $$$[1,5]$$$ and $$$[5,10]$$$.
At temperature $$$6$$$, only the second bear is satisfied — $$$6$$$ is in $$$[5,10]$$$ but not $$$[1,5]$$$.
At temperature $$$11$$$, no bears are satisfied — $$$11$$$ is not in $$$[1,5]$$$ or $$$[5,10]$$$.
While fleeing from his pursuers, the Gingerbread Man shouts, "Run, run as fast as you can! You can't catch me. I'm the Gingerbread Man!"
However, you're not so sure about the Gingerbread Man's claim. Unfortunately for him, he is trying to escape in a busy city with lots of traffic lights.
The city can be thought of as a collection of $$$n$$$ traffic intersections connected by $$$m$$$ two-way roads, where the intersections are numbered from $$$1$$$ to $$$n$$$. The roads are also numbered from $$$1$$$ to $$$m$$$, with the $$$i$$$-th road having a length of $$$l_i$$$ units. The Gingerbread Man runs at a rate of $$$1$$$ unit per second.
The Gingerbread Man is currently at the first intersection and wants to reach intersection $$$n$$$ by traveling through the roads, and he can only pass through an intersection when the traffic light is red; when the light is green, he must wait at the intersection for cars to pass. Initially, all traffic lights have just turned red. The traffic light at the $$$i$$$-th intersection alternates between displaying red for $$$r_i$$$ seconds and green for $$$g_i$$$ seconds. If the Gingerbread Man arrives at the intersection when the light is transitioning from red to green, he must wait.
Since you are skeptical about the Gingerbread Man's ability to run, you would like to figure out the fastest time it takes the Gingerbread Man to reach intersection $$$n$$$. It is guaranteed that a path exists from the first intersection to the $$$n$$$-th intersection.
The first line contains $$$n$$$ ($$$2 \leq n \leq 10^5$$$) and $$$m$$$ ($$$1 \leq m \leq 10^5$$$) — the number of intersections and the number of roads, respectively.
The next $$$n$$$ lines contain two integers each, the $$$i$$$-th of which contains $$$r_i$$$ ($$$1 \leq r_i \leq 10^4$$$) and $$$g_i$$$ ($$$1 \leq g_i \leq 10^4$$$) — the respective durations of red and green lights at intersection $$$i$$$.
The following $$$m$$$ lines contain three integers each, the $$$i$$$-th of which contains $$$u_i$$$ ($$$1 \le u_i \le n$$$), $$$v_i$$$ ($$$1 \le v_i \le n$$$), and $$$l_i$$$ ($$$1 \leq l_i \leq 10^4$$$), indicating a road of length $$$l_i$$$ between intersections $$$u_i$$$ and $$$v_i$$$. It is guaranteed that $$$u_i$$$ and $$$v_i$$$ are distinct.
Output a single integer representing the least amount of seconds it takes the Gingerbread Man to run from intersection $$$1$$$ to intersection $$$n$$$.
3 21 11 11 11 2 12 3 1
3
In the sample, the Gingerbread Man reaches intersection $$$2$$$ after one second, but the light at that intersection turns green when he arrives, so he must wait one second. After waiting, he then takes one second to reach intersection $$$3$$$, so in total he takes at least $$$3$$$ seconds to reach his destination.
As many know from the tale of Hansel and Gretel, they disperse breadcrumbs throughout the forest they're traveling in to make sure they don't get lost. After Gretel's heroics to escape from the witch and return home, the two thought they were done with these adventures. Of course, reality is not always what it seems...
The witch somehow survived the oven, and has magically teleported Hansel and Gretel into a dark room. She warns them that they are about to be teleported into an $$$n$$$ x $$$n$$$ forest. The siblings are presented the following drawing of the forest grid:
- "." denotes an empty space (there are at least two of these)
- "#" denotes an impassable tree
- "E" denotes an exit (there are at least one and most $$$n$$$ of these)
Hansel and Gretel are told that in each of $$$q$$$ simulations, they will be randomly placed in an empty cell. They will be given $$$q_i$$$ breadcrumbs, and they will be required to place a breadcrumb at every cell in the shortest path to an exit (this includes both the "spawn point" and the exit). If Hansel and Gretel fail to reach an exit in any of the queries (i.e. they have too few breadcrumbs), the witch will return the favor and push the siblings into an oven!
Fortunately, Gretel has a machine she created that the witch doesn't know about! Before each simulation, she can input $$$p_i$$$: the probability that Hansel and Gretel can reach the exit from a randomly-selected empty cell if they start with $$$q_i$$$ breadcrumbs. As long as the probability is accurate, the machine will guarantee Hansel and Gretel survive the simulation without the witch knowing. If any probability is wrong... to say the least, they're cooked. Help them survive the forest (again)!
The first line will contain $$$n$$$ ($$$3 \le n \le 1000$$$) and $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$), the size of the forest and the number of queries.
The next $$$n$$$ lines will contain a string of length $$$n$$$, representing a row in the grid with the above key. It is guaranteed there exists at least two "." characters and at least one and at most $$$n$$$ "E" characters in the grid.
The next $$$q$$$ lines each contain one integer $$$q_i$$$ ($$$2 \le q_i \le n^2$$$), the breadcrumbs in the $$$i$$$'th simulation.
Print out $$$q$$$ lines, where the $$$i$$$'th line contains the probability ($$$p_i$$$) for the $$$i$$$'th query. $$$p_i$$$ should have an absolute or relative error of at most $$$10^{-6}$$$, and can be equal to $$$0$$$ or $$$1$$$.
4 3.#....E.##...E..234
0.54545455 0.90909091 1.00000000
5 3E#...##.##...#E...##.....2410
0.00000000 0.00000000 0.00000000
In the first sample, there are 6 empty cells that are 2 breadcrumbs from an exit, 4 cells that are 3 away, and 1 cell that is 4 away. Thus, the respective probabilities are $$$\frac{6}{11}$$$, $$$\frac{10}{11}$$$, and $$$1$$$.
In the second it is impossible to reach an exit, so our probability is always $$$0$$$.
In the magical land of Duloc lies Shrek's beautiful swamp. Shrek is currently in Duloc, but he wants to reach the kingdom of Far Far Away as soon as possible so he can meet Princess Fiona.
There are $$$n$$$ locations in the Shrek universe that are connected by $$$n - 1$$$ bidirectional roads, each of which joins two distinct locations. Location $$$1$$$ is Duloc, and location $$$n$$$ is the kingdom of Far Far Away. It takes Shrek exactly one hour to travel across a single road, and it is guaranteed that Shrek can reach any location from any other location by traveling along a sequence of roads.
His journey isn't this simple however. Some (possible none or all) of the locations in the Shrek universe contain uncooked vegetables. Since Shrek loves uncooked vegetables, he must travel to and eat every uncooked vegetable in the Shrek universe before finishing his journey. Please help Shrek find the minimum number of hours it will take for him to travel from Duloc to the kingdom of Far Far Away while eating every uncooked vegetable in the Shrek universe! Note that this may require him to visit the kingdom of Far Far Away multiple times.
The first line of input will contain the integer $$$n$$$ ($$$2 \leq n \leq 2\cdot10^5$$$) — denoting the number of locations in the Shrek universe.
The second line of input will contain a bitstring $$$s$$$ of length $$$n$$$, where $$$s_i \in \{0, 1\}$$$ is equal to $$$1$$$ if and only if the $$$i$$$-th location contains an uncooked vegetable.
Each of the next $$$n - 1$$$ lines of input will contain two space-separated integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n, a_i \neq b_i$$$) — denoting a road between locations $$$a_i$$$ and $$$b_i$$$.
Output a single integer, indicating the minimum number of hours that it will take for Shrek to complete his journey while eating every uncooked vegetable in the Shrek universe.
5011001 22 42 53 2
4
700001111 24 24 57 47 63 2
7
In the first testcase, there are uncooked vegetables in locations 2 and 3. Shrek can reach all of them by following the path 1 -> 2 -> 3 -> 2 -> 5, which will take him 4 hours. It can be proven that there is no way for Shrek to accomplish this in less time.
In the second testcase, Shrek can follow the path 1 -> 2 -> 4 -> 5 -> 4 -> 7 -> 6 -> 7.
The Big Bad Wolf has just demolished the houses of the First and Second Little Pigs and devoured them, and he is now coming for the Third Little Pig! In less than a minute, the Third Little Pig will need to prepare fortifications with the maximum defensive value possible. To build these fortifications, there are three materials available, each with a unique defensive value. But in order to maximize his odds of survival, the Third Little Pig will need to micromanage every microsecond that can be spent gathering these materials.
- Straw is the easiest material to use; each bushel of straw can be gathered in a fixed amount of time.
- Sticks are more difficult to acquire; each bundle of sticks takes a variable amount of time to collect. The time cost of sticks fluctuates up and down in a repeating pattern and must be paid in sequential order.
- Bricks are the most difficult material to gather; making bricks is back-breaking labor, so the cost of bricks is always increasing. Like sticks, the increase in cost between consecutive bricks is a repeating pattern and must be paid in sequential order.
The defensive value of straw, sticks, and bricks is 1, 2, and 3 respectively. Resources are plentiful in Piglandia, so straw, sticks, and bricks will never run out.
With this knowledge, what is the maximum defensive value the Third Little Pig can attain in $$$t$$$ microseconds?
The first line of input contains $$$t$$$ ($$$0 \le t \le 10^7$$$), the number of microseconds the Third Little Pig has to prepare.
The second line contains $$$c$$$ ($$$1 \le c \le 10^7$$$), the fixed cost of straw.
The third line contains $$$n$$$ ($$$1 \le n \le 10^6$$$), the length of the repeating pattern that represents the time cost of sticks.
The fourth line contains $$$n$$$ integers $$$s_1, s_2, ..., s_n$$$ ($$$1 \le s_i \le 10^7$$$), a series of stick costs that repeats indefinitely.
The fifth line contains $$$b$$$ ($$$1 \le b \le 10^7$$$) and $$$m$$$ ($$$1 \le m \le 10^6$$$), the cost of the first brick and the length of the bricks' repeating pattern.
The sixth line contains $$$m$$$ integers $$$b_1, b_2, ..., b_m$$$ ($$$1 \le b_i \le 10^7$$$), a series of increases in cost between consecutive bricks that repeats indefinitely. For example, the second brick costs $$$b_1$$$ more than the first brick, and the third brick costs $$$b_2$$$ more than the second brick.
The output should be a single integer, the maximum defensive value that the Third Little Pig can attain.
12235 1 13 12
10
Straw will cost 2, 2, 2, ...
Sticks will cost 5, 1, 1, 5, 1, 1, ...
Bricks will cost 3, 5, 7, ...
The optimal choice of materials is 1 straw, 3 sticks, and 1 brick, giving a defensive value of $$$1 \cdot 1 + 3 \cdot 2 + 1 \cdot 3 = 10$$$.
Humpty Dumpty is on the top of his wall. Humpty Dumpty will have some great falls.
The wall can be represented as a two dimensional grid of cells, where $$$(x, y)$$$ denotes a cell in the $$$x$$$-th column from the left of the grid, and $$$y$$$-th row from the bottom of the grid. Some of the cells are fully occupied by 1x1 platforms that fill the entirety of the cell. In particular, any cell of the form $$$(x, 0)$$$ contains a platform. There are also $$$n$$$ additional platforms at other locations.
Humpty Dumpty begins in some cell that isn't occupied by a platform. He may or may not begin directly above a cell with a platform. Humpty's journey follows the following process:
- Suppose Humpty is in cell $$$(x, y)$$$. He will then fall to cell $$$(x, y_2)$$$ such that $$$(x, y_2-1)$$$ contains a platform and none of the cells of the form $$$(k, y)$$$ where $$$y_2 \leq k \leq y$$$ contain a platform. It can be proven that there is exactly one $$$y_2$$$ that satisfies this condition. The ouch factor of his fall is equal to the distance he falls, which is $$$y - y_2$$$.
- Suppose Humpty is now in cell $$$(x, y)$$$. If there is a platform in both cells $$$(x-1, y)$$$ and $$$(x+1, y)$$$, Humpty ends his journey. Otherwise, Humpty must move to either cell $$$(x-1, y)$$$ (if it is not occupied by a platform) or $$$(x+1, y)$$$ (if it is not occupied by a platform). Note that it is possible for Humpty's journey to continue forever.
Humpty's total ouch factor is defined as the maximum ouch factor over all of the falls he makes during his journey.
You are given $$$q$$$ queries. In the $$$i$$$-th query, Humpty will start in the cell $$$(x_i, y_i)$$$. Please find the maximum and minimum total ouch factor across all of the possible paths that Humpty could take in his journey.
The first line contains $$$n$$$, the number of platforms on the wall. $$$0 \leq n \leq 10^5$$$.
The next $$$n$$$ lines contain two integers, $$$x, y$$$, the horizontal and vertical coordinate of the platform. $$$1 \leq x, y \leq 10^5$$$.
The next line contains $$$q$$$, the number of queries. $$$1 \leq q \leq 5 \cdot 10^4$$$.
The next $$$q$$$ lines contain two integers, $$$x, y$$$, the horizontal and vertical coordinate of Humpty's starting point. $$$1 \leq x, y \leq 10^5$$$.
It is guaranteed that all platforms are unique. It is also guaranteed that all query spots are not wall spots.
Output $$$q$$$ lines, with each line containing two integer, the maximum and minimum distance Humpty could fall if he started at the corresponding location.
41 42 33 13 641 52 43 71 3
4 2 2 2 6 3 2 2
51 42 33 34 35 431 55 73 4
4 1 4 2 0 0
For the first sample:
Starting @ $$$(1, 5)$$$: Maximum fall: $$$\textbf{(1, 5)} \rightarrow (0, 1)$$$ Minimum fall: $$$(1, 5) \rightarrow \textbf{(2, 4)} \rightarrow (3, 2) \rightarrow (2, 1)$$$
Starting @ $$$(2, 4)$$$: Maximum fall: $$$\textbf{(2, 4)} \rightarrow (3, 2) \rightarrow (2, 1)$$$ Minimum fall: $$$\textbf{(2, 4)} \rightarrow (3, 2) \rightarrow (2, 1)$$$
Starting @ $$$(3, 7)$$$: Maximum fall: $$$\textbf{(3, 7)} \rightarrow (4, 1)$$$ Minimum fall: $$$\textbf{(3, 7)} \rightarrow (2, 4) \rightarrow (3, 2) \rightarrow (2, 1)$$$
Starting @ $$$(1, 3)$$$: Maximum fall: $$$\textbf{(1, 3)} \rightarrow (1, 1)$$$ Minimum fall: $$$\textbf{(1, 3)} \rightarrow (1, 1)$$$
Bold shows the maximum single fall in each of the sequences, which is also the determining height for the answer.
A fisherman is fishing in the ocean when he encounters a fish in his net. The fish suddenly starts pleading for its freedom. Because the fisherman was feeling a bit generous, he decides to play a game with the fish. The fisherman has some stones, each with some value. After agreeing to some order of stones in a line, the fish and the fisherman take turns taking stones from the left side: the fish takes the first stone, followed by the fisherman taking the second stone, followed by the fish taking the third stone. A player's score at the end is the sum total of values on all the stones they took, and the winner is the player with the larger score (equal value is a tie).
The fisherman already put the stones in some order, but the fish is allowed to rearrange the stones. The fish is not too strong out of the water, so it needs your help! The fish will perform a left cyclic shift on some contiguous subarray of the stones, and then you must answer what the result of the game will be after each query. Note that these updates persist between queries.
A left cyclic shift on some subarray $$$[a_l, a_{l+1}, \dots, a_{r - 1}, a_r]$$$ replaces that subarray with the array $$$[a_{l+1}, \dots, a_{r - 1}, a_r, a_l]$$$ in the original array.
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq q \leq 10^5$$$) — the number of stones and the number of cyclic shifts performed by the fish, respectively.
The next line contains $$$n$$$ integers $$$a_1, a_2, \dots a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the values of the stones in the original order by the fisherman.
Each of the following $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \lt r \leq n$$$) — the left and right endpoints of the subarray
For each query, output "FISH" (without quotes) if the fish will win, "MAN" (without quote) if the fisherman will win, and "TIE" if they will tie.
4 31 2 3 41 23 41 3
TIE FISH MAN
After the first query, the stones are ordered $$$[2, 1, 3, 4]$$$. The fish gets a score of $$$2 + 3 = 5$$$ and the fisherman gets a score of $$$1 + 4 = 5$$$, so they tie.
After the second query, the stones are ordered $$$[2, 1, 4, 3]$$$. The fish gets a score of $$$2 + 4 = 6$$$ and the fisherman gets a score of $$$1 + 3 = 4$$$, so the fish wins.
After the third query, the stones are ordered $$$[1, 3, 2, 4]$$$. The fish gets a score of $$$1 + 2 = 3$$$ and the fisherman gets a score of $$$3 + 4 = 7$$$, so the fisherman wins.
After staying in Wonderland for so long, Alice wants to go back home to catch the next Codeforces Div. 2 round, but the Queen of Hearts has other plans. So, the Queen of Hearts proposes a game for them to play. If Alice wins, she gets to leave, but if she does not, she will stay in Wonderland for one more day, missing out on a potential Grandmaster performance.
In this game, each person will select 2 cards at random from a deck of $$$n$$$ cards, without replacement. The score of a single hand is calculated as the concatenation of the number on the first card and the number on the second card. The winner of the game is the person with the highest score. If the scores are identical, the result is a tie, and neither player wins.
Alice wonders how many different games she will win so that she can prepare herself in advance. Given the numbers in the deck of cards, print out the total number of unique games that she will win. As there can be many winning games, print the result in mod $$$10^9+7$$$.
A game is defined by an ordered set of numbers $$$(c_1,c_2,c_3,c_4)$$$, where $$$c_1$$$ and $$$c_2$$$ are the cards that Alice drew, in that order, and $$$c_3$$$ and $$$c_4$$$ are the cards that the Queen of Hearts drew, in that order. Two games are distinct if there exists an index $$$i$$$ $$$(1\leq i\leq 4)$$$ such that $$$c_i$$$ is different between those games.
The first line contains $$$n$$$ ($$$4\leq n\leq 10^5$$$) — the number of cards.
The second line contains $$$n$$$ unique space-seperated integers $$$a_1, a_2, \dots , a_n$$$ ($$$1\leq a_i\leq 10^9$$$) — the numbers on the cards.
Output a single integer in mod $$$10^9+7$$$, the number of unique games where Alice wins.
41 2 3 4
12
$$$(4,3,2,1)$$$ — Alice gets a score of 43, and the Queen of Hearts gets a score of 21, so Alice wins.
$$$(2,4,1,3)$$$ — Alice gets a score of 24, and the Queen of Hearts gets a score of 13, so Alice wins.
$$$(4,2,1,3)$$$ — Alice gets a score of 42, and the Queen of Hearts gets a score of 13, so Alice wins.
The above games are all unique. In total, there are 12 unique games where Alice wins.