One day, Bob planted a bean in his backyard and was shocked to see a beanstalk start to grow instantly! The beanstalk grew with incredible speed, and seemed to be reaching for a castle in the clouds. Bob immediately started to climb the beanstalk, as it was growing. Bob can climb $$$k$$$ meters upward per minute. Beginning at the start of minute $$$1$$$, the beanstalk will grow for $$$n$$$ minutes until it reaches the castle in the clouds. At the start of the $$$i$$$th minute, the beanstalk will instantly grow $$$b_i$$$ meters. How many minutes will it take Bob to reach the castle in the clouds? If Bob reaches the top before the end of a minute, round up.
The first line will contain the integers $$$n$$$ $$$(1 \leq n \leq 1000)$$$ and $$$k$$$ $$$(1 \leq k \leq 1000)$$$ – the number of minutes the beanstalk will be growing and the number of meters Bob can climb per second.
The next line will contain $$$n$$$ integers, each representing the number of meters $$$b_i$$$ $$$(1 \leq b_i \leq 1000)$$$ the beanstalk will grow at the start of the $$$i$$$th minute.
Output a single integer – the number of minutes it will take Bob to reach the castle in the clouds.
5 32 2 8 12 15
14
In the sample test:
At the start of minute $$$1$$$, the beanstalk grows to height $$$2$$$. Bob climbs $$$2$$$ meters, then waits until the end of the minute for the beanstalk to grow again.
At the start of minute $$$2$$$, the beanstalk grows to height $$$4$$$. Bob climbs to meter $$$4$$$, then waits until the end of the minute for the beanstalk to grow again.
At the start of minute $$$3$$$, the beanstalk grows to height $$$12$$$. Bob climbs to meter $$$7$$$.
At the start of minute $$$4$$$, the beanstalk grows to height $$$24$$$. Bob climbs to meter $$$10$$$.
At the start of minute $$$5$$$, the beanstalk grows to height $$$39$$$. Bob climbs to meter $$$13$$$.
From minutes $$$6$$$ to $$$14$$$, Bob climbs to meter $$$39$$$.
Cinderella is at the royal ball, and is asked to perform a special dance. In this dance, she's going to do a total of $$$n$$$ twirls.
After each twirl, Cinderella will be facing a cardinal direction: North, East, South, or West. During a twirl, Cinderella must choose whether to turn 90 degrees clockwise or counterclockwise to face a new direction. She cannot turn any further than this, and she also cannot stay facing the same direction. Cinderella can also start her dance routine in any location.
The direction that Cinderella faces after each twirl is actually very important. For each "state" after her twirls ($$$n$$$ total), Lady Tremaine has a preferred direction for her to face, stored in $$$s_i$$$, the $$$i$$$th character in a string $$$s$$$ of length $$$n$$$. If Cinderella is facing in the correct direction after a twirl, her wicked stepmother will be very pleased. To maximize the effectiveness of her dance routine, Cinderella wants to match her stepmother's requests as many times as possible.
Help Cinderella maximize the effectiveness of her dance.
The first line contains $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, the number of twirls Cinderella will complete.
The next line contains $$$s$$$, a string of length $$$n$$$ storing the directions Lady Tremaine wishes for Cinderella to face, where the preferred direction for the $$$i$$$th $$$(1 \leq i \leq n)$$$ twirl is stored in $$$s_i$$$. All characters in $$$s$$$ will be 'N', 'S', 'W', or 'E', representing the 4 cardinal directions.
Output a single number, the maximum amount of times Cinderella can face in the preferred direction.
5EWNSE
3
8SEENEWWW
4
In the first test case, one sequence of directions Cinderella can face after each of the dance's twirls is:
E -> S -> W -> S -> E
Cinderella will be in the preferred direction in the 1st, 4th, and 5th states. It can be shown that there are no sequences for which Cinderella faces the preferred direction more than 3 times.
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.
