Everything is bigger in Texas, so of course you want your chicken nuggets to be as big as it can be — but it still has to fit on your plate.
Your chicken nugget is described by $$$n$$$ points in the plane. The $$$i$$$-th point is at integer coordinates $$$(x_i, y_i)$$$ with $$$0 \le x_i, y_i \le 10^9$$$.
You are given an integer scaling factor $$$k$$$. Scaling the chicken nugget by $$$k$$$ moves every point $$$(x_i, y_i)$$$ to $$$(k \cdot x_i,\ k \cdot y_i)$$$. You may translate the chicken nugget after it is scaled, but you may not rotate it.
The plate is an axis-aligned square whose corners are $$$(0, 0)$$$ and $$$(m, m)$$$. The scaled chicken nugget fits on the plate if it is possible to translate it in such a way that every point lies inside the square or on its boundary.
Warning: you may need to use 64 bit integers for this problem!
The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 10^{18}$$$; $$$1 \le k \le 10^9$$$).
Each of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i, y_i \le 10^9$$$) — the coordinates of the $$$i$$$-th point. Points are not necessarily distinct.
If the scaled chicken nuggy does not fit on the plate, print a single line containing -1.
Otherwise print the $$$n$$$ final points of the chicken nugget after scaling and possibly translating, one per line, each as two integers $$$k \cdot x_i$$$ and $$$k \cdot y_i$$$. The points may be printed in any order.
3 10 25 56 75 8
0 0 2 4 0 6
2 5 30 02 2
-1
In the first sample, $$$k = 2$$$, so the points scale to $$$(10, 10)$$$, $$$(12, 14)$$$, and $$$(10, 16)$$$. As they stand they poke off the $$$10 \times 10$$$ billboard, but the scaled logo is only $$$2$$$ wide and $$$6$$$ tall, so shifting it by $$$(-10, -10)$$$ places it at $$$(0, 0)$$$, $$$(2, 4)$$$, $$$(0, 6)$$$ — entirely on the billboard.
In the second sample, $$$k = 3$$$ scales the logo to a $$$6 \times 6$$$ span, which is wider than the side length $$$5$$$, so no translation can make it fit and the answer is -1.
The difference between the versions is the constraint on $$$N$$$.
Although the Red River Rivalry is in Dallas nowadays, Akshaj decided to use the game as motivation to explore the state his new university would (yet again) thrash. While taking a unique route he stumbles upon the Great Prairie Wind Farm. The wind farm contains $$$N$$$ turbines in a row, where the $$$i$$$th turbine has rotation period $$$a_i$$$ seconds.
Akshaj wants to take a picture of these turbines, but he can only do so when they are all aligned in their "neutral" state. A picture is represented by a contiguous subsegment of the turbines, and if Akshaj has to wait longer than $$$T$$$ seconds for alignment he will opt to not take this photograph. Note that at $$$t=0$$$ all of the turbines are aligned at their "neutral" state, but Akshaj must take the photograph at a positive time $$$t \gt 0$$$.
Akshaj wants to make sure he has enough storage, and thus needs to know both how many pictures he can take and their total size. Can you help him out?
The first line contains two integers: $$$N$$$ ($$$1 \le N \le 5000$$$) and $$$T$$$ ($$$1 \le T \le 10^6$$$), the number of turbines and the max time he will wait. The second line contains $$$N$$$ space-separated integers ($$$1 \le a_i \le 10^5$$$), where $$$a_i$$$ is the rotation period of the $$$i$$$th turbine.
Your output should be two space-separate integers $$$C$$$ and $$$S$$$. $$$C$$$ should be the number of pictures he can take, and $$$S$$$ should be the sum of the lengths of all pictures he can take.
4 32 4 1 3
4 5
In the sample test case, the possible pictures he can take (represented by the periods themselves and not the indices) are $$$[2]$$$, $$$[1]$$$, $$$[1,3]$$$, and $$$[3]$$$. The pictures below should help (courtesy of querying Astra with a rough sketch), where the black blade must be pointed directly up to be neutral.
$$$^\dagger$$$Like most things I write, the title of this problem was Kpop-inspired.
On his tour across America, IShowSpeed (aka Darren Watkins Jr.) makes a stop at the legendary Terry Black's Barbecue, a staple of Austin.
The restaurant has $$$n$$$ $$$(1 \le n \le 10^5)$$$ tables arranged in a row, each with either a beef rib on top of it or not. More formally, let $$$s$$$ be a binary string of length $$$n$$$, where $$$s_i = 1$$$ if table $$$i$$$ has a beef rib, and $$$s_i = 0$$$ if table $$$i$$$ does not have a beef rib.
Speed is allowed to make exactly $$$2$$$ runs through the dining area. On each run, he chooses a contiguous range of exactly $$$k$$$ $$$(1 \le k \le n \le 10^5)$$$ tables and eats every rib on those tables. After a run, all ribs on the chosen tables have been eaten, so those tables contain no ribs for any future run. The two ranges are allowed to overlap, but a rib can only be eaten once, so any table included in both ranges contributes at most one rib to Speed's total.
Speed is very hungry after doing backflips and traveling around Austin all day, so he wants to maximize the number of beef ribs he eats. Help Speed figure out the maximum amount of beef ribs he can eat if he chooses where to make his runs optimally.
The first line contains integers $$$n, k$$$ $$$(1 \le k \le n \le 10^5)$$$, the total number of tables and the number of tables Speed goes through in a run respectively.
The second line contains $$$s$$$, a binary string of length $$$n$$$, representing which tables contain dino ribs
Output a single number, the total number of ribs Speed can eat if he chooses where to make his runs optimally.
11 301110100110
5
In the first test case, the answer is 5 as you can choose the two runs of size 3 ($$$k = 3$$$) as follows (the brackets here encapsulate where the runs are chosen)
$$$0[111]010[011]0$$$
Clearly, the sum of 1s in these two intervals is 5.
Note that in this case the intervals are disjoint, but this is not a requirement.
One day, Johnny thought of a non-negative integer $$$n$$$, but unfortunately, he thinks the number is too small.
To make the number bigger, Johnny decides to make the number a Texas-Sized Number. To find the Texas-Sized Number of $$$n$$$, Johnny must calculate $$$$$$n + 10 \cdot n + 100 \cdot n + 1000 \cdot n + ... + 10^{10^{10}} \cdot n.$$$$$$
However, because this number takes too long to calculate, Johnny is only interested in the most common digit in the Texas-Sized Number of $$$n$$$. Can you help him find this digit?
The first line contains one non-negative integer $$$n$$$ — the number that Johnny thought of. This integer can be up to $$$10^5$$$ digits long.
Output a single integer — the most common digit in the Texas-Sized Number of $$$n$$$. If there is a tie, output any most common digit.
0
0
12
3
Cowboy Dance, Jenne Magafan, 1941. At a Texas dance hall, $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) dancers are practicing the two-step. The dancers are numbered from $$$1$$$ to $$$n$$$, and each begins facing either left or right.
Dancer $$$i$$$ is a little particular: they only feel comfortable if at least $$$i$$$ remaining dancers, including themself, are facing the same direction.
The dance proceeds in beats. At the beginning of each beat, every remaining dancer counts how many dancers are facing the same direction as them.
If dancer $$$i$$$ sees fewer than $$$i$$$ dancers facing their direction, they get self-conscious. The first time this happens, they turn around, hoping to fit in better with the other side. If it happens again after they have already turned once, they give up and leave the dance floor.
All dancers make their decisions using the configuration at the beginning of the beat, and all actions happen simultaneously.
The dance ends when a beat passes in which nobody turns around or leaves.
Find the number of dancers remaining on the dance floor.
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$)—the number of dancers.
The second line contains a string $$$s$$$ of length $$$n$$$, consisting only of the characters L and R.
The $$$i$$$-th character of $$$s$$$ describes the initial direction of dancer $$$i$$$. If $$$s_i$$$ is L, dancer $$$i$$$ initially faces left; otherwise, dancer $$$i$$$ initially faces right.
Print a single integer—the number of dancers remaining when the dance ends.
5LLRLR
3
Initially, dancers $$$3$$$, $$$4$$$, and $$$5$$$ are uncomfortable, so they turn around.
On the next beat, dancers $$$4$$$ and $$$5$$$ are uncomfortable again and leave the dance floor.
The remaining dancers $$$1$$$, $$$2$$$, and $$$3$$$ are all comfortable, so the dance ends with $$$3$$$ dancers remaining.
(The only difference between the easy and hard versions is the constraint on $$$n$$$.)
It's game day, and students are in DKR, eagerly watching the scoreboard clock counting down to kickoff. The countdown is displayed as $$$n$$$ mechanical flip-digit indicators, each showing a digit from $$$0-9$$$.
The clock is weird; when the display ticks down from $$$t$$$ to $$$t-1$$$, the digits do not flip all instantly. Instead, each digit that needs to change takes 1 second to flip. But digits can only be flipped once at a time.
So, for instance, if the clock ticks down from $$$\mathbf{67}$$$ to $$$\mathbf{66}$$$, it only takes 1 second, as only one digit changed. But if the clock ticks down from $$$\mathbf{900}$$$ to $$$\mathbf{899}$$$, it takes 3 seconds, as three digits changed.
Given how many seconds are currently displayed on the clock, the students are wondering how many actual seconds it will take until kickoff (when the clock has all digits showing $$$0$$$).
The first line will contain $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, the number of digits of the number.
The second line will be a string of $$$n$$$ digits, the current display on the clock. It is guaranteed that at least one digit is not zero.
Print a single integer without leading zeros, the number of actual seconds left until kickoff. Note that this number can be huge.
267
73
3003
3
512345
13715
11
1
30116605222020078348307278321906
129561357800087053674753690995
In the first example, there are 6 changes that take 2 seconds: $$$60$$$ to $$$59$$$, $$$50$$$ to $$$49$$$, $$$40$$$ to $$$39$$$, $$$30$$$ to $$$29$$$, $$$20$$$ to $$$19$$$, and $$$10$$$ to $$$09$$$. So, the total time is $$$2(6) + 1(67-6) = 73$$$.
The difference between the versions is the constraint on $$$N$$$.
Although the Red River Rivalry is in Dallas nowadays, Akshaj decided to use the game as motivation to explore the state his new university would (yet again) thrash. While taking a unique route he stumbles upon the Great Prairie Wind Farm. The wind farm contains $$$N$$$ turbines in a row, where the $$$i$$$th turbine has rotation period $$$a_i$$$ seconds.
Akshaj wants to take a picture of these turbines, but he can only do so when they are all aligned in their "neutral" state. A picture is represented by a contiguous subsegment of the turbines, and if Akshaj has to wait longer than $$$T$$$ seconds for alignment he will opt to not take this photograph. Note that at $$$t=0$$$ all of the turbines are aligned at their "neutral" state, but Akshaj must take the photograph at a positive time $$$t \gt 0$$$.
Akshaj wants to make sure he has enough storage, and thus needs to know both how many pictures he can take and their total size. Can you help him out?
The first line contains two integers: $$$N$$$ ($$$1 \le N \le 10^5$$$) and $$$T$$$ ($$$1 \le T \le 10^6$$$), the number of turbines and the max time he will wait. The second line contains $$$N$$$ space-separated integers ($$$1 \le a_i \le 10^5$$$), where $$$a_i$$$ is the rotation period of the $$$i$$$th turbine.
Your output should be two space-separate integers $$$C$$$ and $$$S$$$. $$$C$$$ should be the number of pictures he can take, and $$$S$$$ should be the sum of the lengths of all pictures he can take.
4 32 4 1 3
4 5
In the sample test case, the possible pictures he can take (represented by the periods themselves and not the indices) are $$$[2]$$$, $$$[1]$$$, $$$[1,3]$$$, and $$$[3]$$$. The pictures below should help (courtesy of querying Astra with a rough sketch), where the black blade must be pointed directly up to be neutral.
$$$^\dagger$$$Like most things I write, the title of this problem was Kpop-inspired.
The biggest football game of the year is almost here, and exactly one ticket remains. There are $$$n$$$ people hoping to receive it.
The organizer assigns each person a positive relative weight. If the relative weights are $$$w_1,w_2,\ldots,w_n$$$, then the probability that person $$$i$$$ receives the ticket is
$$$$$$\frac{w_i}{\sum_{j=1}^{n}w_j}.$$$$$$
Rather than storing the weights directly, the organizer stores $$$n-1$$$ ratios $$$a_1,\ldots,a_{n-1}$$$. For each $$$1\le i \lt n$$$, person $$$i$$$ is $$$a_i$$$ times as likely to receive the ticket as person $$$i+1$$$. Equivalently, their weights satisfy
$$$$$$w_i=a_iw_{i+1}.$$$$$$
The ratios change over time. You must process $$$q$$$ queries:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2\le n\le 2\cdot10^5$$$, $$$1\le q\le2\cdot10^5$$$) — the number of people and the number of queries, respectively.
The second line contains $$$n-1$$$ integers $$$a_1,a_2,\ldots,a_{n-1}$$$ ($$$1\le a_i \lt 10^9+7$$$) — the initial likelihood ratios between consecutive people.
Each of the next $$$q$$$ lines describes a query in one of the following formats:
For each query of the second form, let the requested probability be $$$\frac{p}{r}$$$. If $$$r$$$ is divisible by $$$10^9+7$$$, print $$$\texttt{-1}$$$. Otherwise, print
$$$$$$p\cdot r^{-1}\bmod (10^9+7),$$$$$$
where $$$r^{-1}$$$ is the modular multiplicative inverse of $$$r$$$ modulo $$$10^9+7$$$.
4 52 3 42 12 41 2 12 12 3
804878055 658536590 823529418 411764709
Initially, choose $$$w_4=1$$$. Then the relative weights are $$$(24,12,4,1)$$$ and their sum is $$$41$$$. Thus, the first two queried probabilities are $$$\frac{24}{41}$$$ and $$$\frac{1}{41}$$$.
After setting $$$a_2=1$$$, the weights become $$$(8,4,4,1)$$$ with sum $$$17$$$. The final two queried probabilities are $$$\frac{8}{17}$$$ and $$$\frac{4}{17}$$$.