Edward is really really thirsty and he wants to drink $$$n$$$ cups of hot cocoa.
Each of these cups have an associated heat, but decrease by $$$d$$$ heat every second.
Since Edward is really really really thirsty, he can consume hot cocoa instantly once the temperature of a cup drops equal to or below $$$h$$$.
What is the earliest time that Edward can satiate his thirst by finishing all cups of cocoa?
The first line contains $$$n$$$ the number of cups, $$$d$$$ the rate that the cups cool down, and $$$h$$$ the temperature for Edward to consume the cup. $$$1 \leq n, d, h \leq 10^5 $$$
The second line contains $$$n$$$ integers, $$$c_1, c_2, ..., c_n$$$, representing the initial heat of the cups. $$$1 \leq c_i \leq 10^9$$$
Output one integer $$$t$$$, the first time in which Edward can finish all the cups.
3 2 11 4 2
2
In the sample testcase, Edward can consume the first mug at $$$t=0$$$, the second at $$$t=2$$$, and the third at $$$t=1$$$.
Magikarp wants to create perfectly shaped snowballs with his $$$n$$$ friends. To do this, he tells his friends to make a chain to speed up this process.
Magikarp's friends are numbered from $$$1$$$ to $$$n$$$, inclusive, and they are lined up in order of their number, with $$$1$$$ on the very left and $$$n$$$ on the very right. Each friend can take one snowball from the friend on their left, process it in $$$a_i$$$ seconds, and pass it to the friend on their right. Each friend can only process one snowball at a time, and they will do this optimally.
Assuming that there is an infinite pile of snowballs to the left of friend $$$1$$$, how many finished snowballs are produced by friend $$$n$$$ in $$$t$$$ seconds?
The first line of input contains $$$n$$$ an $$$t$$$ $$$(1\le n\le 2\cdot 10^5, 1\le t\le 10^9)$$$ — the number of friends, and the total time in seconds.
The second line of input contains $$$a_1,a_2,\ldots,a_n$$$ $$$(1\le a_i\le 10^9)$$$ — the time it takes for each friend to process one snowball.
Output a single integer, the number of finished snowballs produced after $$$t$$$ seconds.
5 251 4 2 3 4
3
2 101 1
9
In the second testcase, the first snowball gets processed by the first friend at $$$t=1$$$. It is then finished at $$$t=2$$$. The second snowball gets processed by the first friend at $$$t=2$$$ and gets finished at $$$t=3$$$. This process repeats 9 times for 9 finished snowballs. Note that when $$$t=10$$$, the first friend has finished processing a 10th snowball, but since it has not passed through all the friends, it is not counted.
As the southern US prepares for the weekend's ice freeze, and the City of Austin has hired a surveyor to help you ensure all the highway markers are set up properly for drivers. Unfortunately the surveyor is nowhere near Austin, so the best way they can help is a virtual Zoom conference to ensure all the highway markers are set up properly.
The highway has $$$n$$$ markers indexed from $$$1$$$ to $$$n$$$, and a marker of height $$$h_i$$$ is "stable" if $$$\gcd(h_i, i) = 1$$$. The markers do not necessarily have to all be stable, so your surveyor will instead provide you a set of $$$q$$$ queries in the form $$$(l,r)$$$, and you need to respond ASAP with how many stable markers are in the interval $$$[l,r]$$$ (inclusive). Get this done as soon as possible to prevent overfreezing!
The first line contains two numbers, $$$n$$$ and $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le q \le 10^4$$$), the number of markers on the highway and the number of queries respectively. The second line contains the array $$$h$$$ of $$$n$$$ integers, where $$$h_i$$$ denotes the height of the $$$i$$$th marker ($$$1 \le h_i \le 10^6$$$). The next $$$q$$$ lines each contain two numbers $$$l$$$ and $$$r$$$ ($$$1 \le l \lt r \le n$$$), denoting the query as described in the problem statement.
Print $$$q$$$ integers, where the $$$i$$$th integer represents the answer to query $$$i$$$: the number of stable markers between $$$l_i$$$ and $$$r_i$$$ inclusive.
5 38 6 5 4 103 42 31 5
1 1 2
Oh no! A graveyard has appeared and skeletons are attacking Ken's precious tower! More specifically, Ken is under siege for $$$k$$$ $$$(1 \leq k \leq 10^9)$$$ seconds facing a total of $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ skeletons, where skeleton $$$i$$$ will spawn at time $$$a_i$$$. In order to try and defend his tower, Ken can use a powerful snowball, which kills all skeletons that have already spawned at once! However, Ken only has one snowball, so he must choose wisely when to use it!
At each second $$$x$$$ between $$$0 \dots k - 1$$$, the following occurs in order:
- Any skeletons scheduled to spawn at time $$$x$$$ spawn in
- If Ken uses his snowball at this time, the snowball is launched, instantly killing all alive skeletons
- Each alive skeleton attacks Ken's tower, dealing 1 damage.
Help Ken find the minimum damage that his tower will take after the siege is over across all times at which he can use his snowball.
The first line contains two integers, $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ and $$$k$$$ $$$(1 \leq k \leq 10^9)$$$, where $$$n$$$ is the size of $$$a$$$ and $$$k$$$ is how long the siege lasts for.
The second line contains $$$n$$$ integers, $$$[a_1, a_2, ... a_n]$$$ $$$(0 \leq a_i \leq k - 1)$$$, the times at which each skeleton spawns
Output one number, the minimum damage done to Ken's tower after the siege is over across all times at which he can use his snowball.
2 30 1
1
4 100 9 9 9
3
In the first test case, if Ken uses the snowball at time $$$1$$$, both skeletons have spawned and are thus killed. In total, the skeleton that spawns at time $$$0$$$ does $$$1$$$ damage, and this is all.
In the second test case, if Ken uses the snowball at time $$$0$$$, the first skeleton is killed. The total damage is $$$3$$$, as $$$3$$$ more skeletons spawn in afterwards at time $$$9$$$, but they only have time for one attack before the siege ends.
Snowflakes often appear to have six-fold radial symmetry due to the hexagonal crystalline structure of ice. C.C., amazed by this fact, collects the most interesting snowflakes she can find across UT. Examining them with a microscope, she finds certain rare ones break this six-fold symmetry. Help her identify these snowfakes!
C.C. maps the snowflake's vertices onto a unique coordinate grid, with the snowflake centered at the origin $$$(0,0)$$$. Rather than the traditional Cartesian grid, she uses two unit vectors separated by an angle of $$$60^\circ$$$:
- $$$\mathbf{e_1}$$$ lies along the positive x-axis.
- $$$\mathbf{e_2}$$$ is rotated $$$60^\circ$$$ counter-clockwise from $$$\mathbf{e_1}$$$.
A point recorded as $$$(u, v)$$$ represents the position $$$u \cdot \mathbf{e_1} + v \cdot \mathbf{e_2}$$$. This grid lends itself to the nature of snowflakes—all points can be represented with integer coordinates!
A snowflake is considered perfect if rotating the set of points by $$$60^\circ$$$ around the origin results in the exact same set of points. Given $$$1 \le N \le 10^5$$$ points, determine if C.C. has found a perfect snowflake.
The first line of input contains an integer $$$N$$$ ($$$1 \le N \le 10^5$$$) — the number of vertices in the snowflake.
Each of the next $$$N$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$-10^9 \le u_i, v_i \le 10^9$$$) — the coordinates of the $$$i$$$-th vertex in C.C.'s grid system. It is guaranteed that all $$$N$$$ points are distinct.
Print a single line containing the string "YES" if the snowflake is perfect (i.e., it has 6-fold rotational symmetry about the origin), or "NO" otherwise.
70 02 1-1 3-3 2-2 -11 -23 -2
NO
70 02 1-1 3-3 2-2 -11 -33 -2
YES
The purple points below describe the first test case's not perfect snowflake. The vectors $$$\mathbf{e_1}$$$ and $$$\mathbf{e_2}$$$ are shown in red and blue, respectively.
The difference between this and the easier problem is the constraint being queried on.
As the southern US prepares for the weekend's ice freeze, and the City of Austin has hired a surveyor to help you ensure all the highway markers are set up properly for drivers. Unfortunately the surveyor is nowhere near Austin, so the best way they can help is a virtual Zoom conference to ensure all the highway markers are set up properly.
The highway has $$$n$$$ markers indexed from $$$1$$$ to $$$n$$$, each with a height $$$h_i$$$. The surveyor has realized that different parts of the highway have a lot of differences, from the weather conditions of nearby cities to the materials used. In each of $$$q$$$ queries, he will provide you with the numbers $$$l$$$, $$$r$$$, and $$$k$$$, and needs to know how many markers in the interval $$$[l,r]$$$ satisfy $$$k \mid \gcd(h_i, i)^\dagger$$$. Help him out (again) ASAP, before the roads collapse!
$$$^\dagger$$$The notation $$$a\mid b$$$ denotes that $$$a$$$ divides $$$b$$$ (or $$$b$$$ is divisible by $$$a$$$), meaning there exists an integer $$$k$$$ such that $$$ka = b$$$. For instance, $$$3 \mid 6$$$, but $$$4 \nmid 7$$$.
The first line contains two numbers, $$$n$$$ and $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le q \le 10^4$$$), the number of markers on the highway and the number of queries respectively. The second line contains the array $$$h$$$ of $$$n$$$ integers, where $$$h_i$$$ denotes the height of the $$$i$$$th marker ($$$1 \le h_i \le 10^6$$$). The next $$$q$$$ lines each contain three numbers, $$$l$$$ $$$r$$$ and $$$k$$$ ($$$1 \le l \lt r \le n$$$, $$$1 \le k \le 10^3$$$), denoting the query as described in the problem statement.
Print $$$q$$$ integers, where the $$$j$$$th integer represents the answer to query $$$j$$$.
5 58 6 5 4 103 4 12 3 21 5 11 5 21 5 5
2 1 5 2 1
With twenty years of professional skiing under his belt, Johnny decides to take his skills to the next level at the annual Ski-Bidi obstacle course.
The Ski-Bidi obstacle course this year lies on a large hill with a length of $$$n$$$ feet and $$$m$$$ lanes. In other words, it can be thought of as an $$$n$$$ by $$$m$$$ grid. On the hill, there are $$$k$$$ obstacles, where the $$$i$$$-th obstacle lies at $$$(r_i, c_i)$$$.
Johnny is allowed to start at the top of the hill at any lane – that is, any point of the form $$$(1, c)$$$ where $$$1 \le c \le m$$$. In one second, he moves down the hill by $$$1$$$ foot and can either stay in the current lane or move to an adjacent lane as long as he does not collide with an obstacle. In other words, Johnny can move from $$$(r, c)$$$ to $$$(r + 1, c)$$$, $$$(r + 1, c - 1)$$$, or $$$(r + 1, c + 1)$$$, as long as his new location does not lie on an obstacle or leaves the grid.
As Johnny wants to finish in style, he wants to know what lanes he can end the obstacle course in. In particular, after $$$n - 1$$$ seconds, which lanes can Johnny be in?
The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \le n \le 10^9$$$, $$$1 \le m \le 10^5$$$, $$$1 \le k \le 2 \cdot 10^5$$$) – the length of the obstacle course, the number of lanes in the obstacle course, and the number of obstacles, respectively.
The next $$$k$$$ lines each contain two integers, with the $$$i$$$-th line containing $$$r_i$$$ and $$$c_i$$$ ($$$2 \le r_i \le n$$$, $$$1 \le c_i \le m$$$) – the location of the $$$i$$$-th obstacle. It is guaranteed that the locations of the obstacles are distinct.
On the first line, output the number of lanes that Johnny can end the obstacle course in. On the second line, output the aforementioned lanes as an increasing list of space-separated integers.
4 3 23 13 2
2 2 3
4 4 62 22 32 44 14 24 3
0
In the first sample test case, in order to reach the end of the obstacle course, Johnny must be in lane $$$3$$$ after skiing for two seconds. He is then free to move to either lane $$$2$$$ or stay in lane $$$3$$$ at the end of the obstacle course.
In the second sample test case, Johnny cannot reach the end of the obstacle course, as doing so would require moving from lane $$$1$$$ to lane $$$4$$$ in $$$2$$$ seconds.
Eddie wants to build a snowman. In front of him is a field of snow, represented by an array $$$d$$$ of size $$$n$$$ where $$$d[i]$$$ is the depth of the snow at position $$$i$$$. Eddie can make a snowball by rolling together the snow in an interval $$$[x, y]$$$, where the size of the resulting ball is $$$s = \sum_{i=x}^y d[i]$$$. Eddie wants to make a three-ball snowman from three intervals $$$[1, l]$$$, $$$[l+1, r]$$$, and $$$[r+1, n]$$$ such that if the sizes of the balls are sorted as $$$s_1 \le s_2 \le s_3$$$, then $$$s_2 \ge 2s_1$$$ and $$$s_3 \ge 2s_2$$$. Eddie also wants a big snowman, so the value of $$$s_1$$$ should be as large as possible.
Can you help Eddie build a snowman meeting his requirements so that the size of the smallest snowball in the snowman is maximized?
The first line of input contains $$$n$$$ ($$$3 \le n \le 10^5$$$), the size of the snow field.
The second line contains $$$n$$$ integers, $$$d_1, d_2, ..., d_n$$$ ($$$1 \le d_i \le 10^9$$$), the depth of the snow at each position.
The output should be one line containing the maximum possible size of the smallest snowball in a valid snowman, or $$$-1$$$ if no valid snowman can be constructed.
42 1 1 3
1
Eddie can only build a valid snowman from the three intervals $$$[1, 1]$$$, $$$[2, 2]$$$, and $$$[3, 4]$$$. This results in a snowman with snowballs of size $$$2$$$, $$$1$$$, and $$$1+3=4$$$, so the smallest snowball is of size $$$1$$$.
A blizzard has just hit the North Pole and the main road has been covered with lots of snow! Formally, the road has $$$n$$$ segments, numbered $$$1\ldots n$$$, and the $$$i$$$th segment has a height of $$$h_i$$$ in inches. We can assume that there are road segments at positions $$$0$$$ and $$$n+1$$$ and that they both of height $$$0$$$. Santa needs the road cleared asap but he can only clear the snow by using his magic snow plow. To use the plow, he can place it on some segment along the road, and reduce the height of an higher adjacent cell until it is equal to the lower one. The time it takes to do this is equal to the square of the absolute difference between the cell that the plow is on and the cell whose height is being reduced.
Formally, for one operation choose $$$i$$$ and $$$j$$$ such that $$$0 \leq i, j \leq n + 1$$$, $$$|i - j| = 1$$$, and $$$h_i \lt h_j$$$. The operation takes $$$(h_j - h_i)^2$$$ minutes. Then, change the value of $$$h_j$$$ to $$$h_i$$$.
The total time taken to clear the road is equal to the sum of the time taken during each operation. Help Santa by finding the minimum time needed to clear the road.
The first line of input will contain a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$)— representing the number of road segments.
The next line will contain $$$n$$$ integers $$$h_1, ..., h_n$$$ ($$$1 \leq h_i \leq 10^6$$$) — $$$h_i$$$ denoting the height in inches of the $$$i$$$th road segment.
Output a single integer on its own line denoting the minimum time needed to clear all of the snow.
51 2 4 3 1
11
41 4 3 3
17
51000000 1 1000000 1000000 1
2999994000008