It's trick-or-treating time, and since Randy is too lazy to hand out candy, he has placed a bowl of candy outside of his door. Knowing that there are many kids in his neighborhood, Randy plans to fill this bowl $$$k$$$ times over the course of the evening, where each time he fills the bowl up to its maximum capacity of $$$c$$$ pieces of candy. Note that initially the bowl is empty.
To keep the bowl from being emptied too quickly, Randy has placed a label on the bowl which says "Take One". As expected, however, not every trick-or-treater follows Randy's one candy rule. In particular, there are two types of kids in Randy's neighborhood: good kids, who actually take one piece of candy (if there is candy remaining), and evil kids, who will take everything from the bowl.
Having been a good kid in the past, Randy wants to make sure the good kids get more candy. Given a sequence of $$$n$$$ kids who arrive at Randy's doorway for candy at distinct times, can you help Randy find the maximum amount of candy that the good kids take from his bowl?
The first line contains three integers $$$n$$$, $$$c$$$, and $$$k$$$ ($$$1 \le n, c, k \le 10^5$$$) – the number of kids who will arrive at Randy's doorway for candy, the capacity of Randy's candy bowl, and the number of times Randy will fill the bowl with candy.
The second line contains $$$n$$$ space-separated integers, where the $$$i$$$-th integer is $$$1$$$ if the $$$i$$$-th kid to arrive is good and $$$0$$$ if the $$$i$$$-th kid is bad.
Output a single integer – the maximum amount of candy that Randy can give away to good kids.
5 4 11 1 1 0 0
3
In the sample test case, Randy can fill the bowl before the first kid arrives. Then the first three kids (who are all good) will each take one piece of candy, the fourth kid will take the remaining piece of candy, and the fifth kid will have no candy to take. This allows Randy to give three pieces of candy away to good kids, which is the maximum amount possible.
Karpsburg is a neighborhood made of $$$n$$$ houses, each of which has a house number $$$a_i$$$. For every pair of houses, there is a bidirectional road between them. For all $$$1\le i \lt j\le n$$$, there is a bidirectional sidewalk between houses $$$i$$$ and $$$j$$$ if and only if there exists a positive integer $$$k \gt 1$$$ such that $$$a_i\equiv a_j \pmod k$$$. Roads can only be traversed by car, and sidewalks can only be traversed by walking.
Magikarp wants to go trick-or-treating in Karpsburg, but he does not want to drive very much. Magikarp starts at a house of his choice. From here, he may either walk along a sidewalk or drive along a road to another house.
What is the minimum number of times that Magikarp must drive for him to visit every house exactly once?
The first line of input contains $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — the number of houses.
The second line of input contains $$$n$$$ space-seperated integers, $$$a_1, a_2, \ldots ,a_n$$$ ($$$1\le a_i\le 10^9$$$) — the house numbers of the $$$n$$$ houses. It is not guaranteed that all house numbers are distinct.
Output a single integer, the minimum number of times that Magikarp must drive.
51 3 4 8 9
0
26 7
1
A haunted pumpkin has landed in Alice's backyard, just in time for Halloween! It has the spooky property of spreading: Every night, the amount of pumpkins in Alice's backyard will double, until she casts a spell to end the process. Alice doesn't want to disenchant the pumpkin yet, she would like to have exactly $$$n$$$ pumpkins in her backyard first. She can also do some work in her yard to remove pumpkins, removing up to $$$k$$$ pumpkins every day.
Thus, every day, Alice may choose to do one of the following:
Find the minimum amount of days for Alice to reach her goal of her garden ending up with $$$n$$$ pumpkins! Note that she must always cast the spell to stop the doubling exactly once.
The integers $$$n$$$ ($$$1 \leq n \leq 1000$$$) and $$$k$$$ $$$(1 \leq k \leq 1000)$$$, the number of pumpkins Alice wants, and the amount she can remove every day. There is initially 1 pumpkin.
Output a single integer, the minimum number of days for Alice to reach $$$n$$$ pumpkins.
7 1
5
10 2
5
1 1000
1
In the first case, the optimal answer is 5. Alice should let the pumpkins double for 3 days, getting to 8 pumpkins. On day 4, she should cast the spell to stop the doubling, remaining at 8 pumpkins. On day 5, she should remove 1 pumpkin.
In the second case, the optimal answer is 5. Alice should let the pumpkins double for 2 days, getting to 4 pumpkins. On day 3, she should remove a pumpkin, going down to 3, which then doubles to 6. On day 4, she should remove a pumpkin, going down to 5, which then doubles to 10. On day 5, she should cast the spell to stop the doubling.
In the third case, the optimal answer is 1. Alice has 1 pumpkin, and should cast the spell to stop the doubling.
As part of Halloween tradition, Cookie Sigma is going trick or treating (even though he might be a little too old for it now)! Specifically, he is trick or treating on Permutation Avenue, where the addresses of all of the houses are a permutation!
More formally, there is a permutation* $$$a$$$ of $$$n$$$ $$$(2 \leq n \leq 5000)$$$ houses, where $$$a_i$$$ is the address of house $$$i$$$.
As a number enthusiast, Cookie Sigma wants to visit the houses in increasing order of their addresses — that is, he wants to visit address $$$1$$$, then $$$2$$$, and so on, up to $$$n$$$. However, going strictly in that order can be very inefficient, since the houses might be far apart on the street.
To make his route shorter, Cookie Sigma can perform at most one swap in his visiting order — meaning he may choose two addresses and swap the order in which he visits them (possibly performing no swap at all).
The total distance Cookie Sigma has to travel is the sum of distances between consecutive houses in his visiting order. Formally, if the $$$x$$$-th house Cookie Sigma visits is located at index $$$p_x$$$, then the total distance is defined as:
Total Distance = $$$\sum_{x=1}^{n-1} |p_{x+1} - p_x|$$$.
Note that Cookie Sigma starts at the first house he plans on visiting, so there is no travel cost to get there.
Find the minimum total distance he can achieve.
* A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2, 3, 1, 5, 4]$$$ is a permutation, but $$$[1, 2, 2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1, 3, 4]$$$ is also not a permutation ($$$n = 3$$$ but there is $$$4$$$ in the array).
The first line contains an integer $$$n$$$ $$$(2 \leq n \leq 5000)$$$ — the number of houses on Permutation Avenue
The second line contains $$$n$$$ numbers, $$$a_1, a_2, \dots, a_n$$$ $$$(1 \leq a_i \leq n)$$$ — the addresses of the houses on Permutation Avenue
Output a single number, the minimum total distance Cookie Sigma can achieve.
42 4 1 3
5
41 2 3 4
3
In the first test case, we can swap when we go to house $$$1$$$ and $$$4$$$, meaning our visiting order is $$$[4, 2, 3, 1]$$$.
It can be proven that this is the minimum total distance we can achieve.
In the second test case, we can leave our visiting order as is and perform no swaps. Going in order yields a total distance of $$$3$$$ which is optimal.
The Hallway of Horrors is an infamous haunted house that consists of a single corridor filled with terrifying traps and surprises. Without fully understanding what he was getting into, Johnny entered the Hallway and encountered his first jumpscare. Now, he wants to leave, but he can only go forward, deeper into the Hallway of Horrors...
The Hallway of Horrors consists of a series of $$$n$$$ jumpscares in a row, where the jumpscare at index $$$i$$$ occurs once every $$$s_i$$$ timesteps — specifically when the time $$$t$$$ is a multiple of $$$s_i$$$ — with a scare value of $$$v_i$$$. Note that Johnny can experience the same jumpscare multiple times. Johnny starts at index $$$1$$$ at $$$t = 0$$$ having experienced the first jumpscare, and his goal is to reach the exit at index $$$n+1$$$. At every timestep, he can either move forward or stay still, but staying still will heighten Johnny's nerves, adding $$$w$$$ to Johnny's scare value.
Please help Johnny escape the Hallway of Horrors with the lowest cumulative scare value possible.
The first line of input contains $$$n$$$ and $$$w$$$ ($$$1 \le n \le 10^3, 1 \le w \le 10$$$), the number of jumpscares and the scare value of staying still, respectively.
The second line contains $$$n$$$ integers, $$$s_1, s_2, ..., s_n$$$ ($$$1 \le s_i \le 10^3$$$), the period of repetition of each jumpscare.
The third line contains $$$n$$$ integers, $$$v_1, v_2, ..., v_n$$$ ($$$1 \le v_i \le 10$$$), the scare value of each jumpscare.
The output should be one line containing the minimum possible scare value Johnny can accumulate by the time he reaches the exit.
3 12 1 21 2 3
4
Johnny starts with a scare value of $$$1$$$ from the first jumpscare at $$$t = 0$$$. Next, it is optimal to wait for one timestep at a cost of $$$1$$$, then move forward $$$3$$$ times, which will result in one jumpscare at index $$$2$$$. This gives a cumulative scare value of $$$1 + 1 + 2 = 4$$$.
In the still darkness before dawn, when the air is heavy and the streets lie empty, a distant rhythm begins — tung… tung… tung… The sound echoes through narrow alleys, growing louder with every strike of the drum. It is the call for sahur, they say, a reminder to awaken and eat before the first light. Yet those who have heard it too late in the night whisper that sometimes the drummers are unseen, their footsteps leaving no trace, their beats coming from nowhere and everywhere at once. The tung tung tung drifts through fog and silence, a hollow heartbeat of something ancient that stirs only when the world sleeps deepest.
You lie awake, in the sleeping town of Al-Mahr, just before dawn. The air trembles with the distant tung… tung… tung… of the sahur drums. The axis-aligned alleys — narrow, twisting veins of stone — form a strange grid: some running North–South, others East–West, all shrouded in mist. The villagers whisper that when the drummers wander too far, their echo becomes trapped between the walls, circling endlessly through the crossroads.
Some say it's merely a trick of geometry, with the alleys connecting to each other, forming infinite loops where the sounds could wander endlessly. Other say it's an age old curse, where the droning sound of the drums forever torments the village.
Your task is to trace these alleys and decide: is it possible that the rhythm of tung tung tung is forever trapped in a ghastly loop among the alleys?
The first line contains $$$N$$$ the number of alleys. $$$1 \leq N \leq 10^3$$$.
The next $$$N$$$ lines contain 4 integers each, $$$x_1, y_1, x_2, y_2$$$, representing the starting and ending points of each alley. $$$1 \leq x_1, y_1, x_2, y_2 \leq 10^6 $$$
It is guaranteed that $$$x_1 = x_2$$$ or $$$y_1 = y_2$$$ for every alley.
It is also guaranteed that no two alleys overlap other than possibly an intersection.
Output "YES" if it is possible for the sound of tung tung tung to wander forever in the alleys, otherwise "NO". It is possible for the sound to wander forever in the alleys if there is an infinite path that the sound can take in the alleys where it never takes a $$$180$$$ degree turn on itself.
4 0 0 0 4 3 0 3 4 4 3 0 3 0 1 4 1
YES
Epilogue
And so, as the final alley was traced beneath the pallid moonlight, the rhythm began again — tung… tung… tung… — steady and slow, echoing between the stones. The cycle was real, not just in geometry, but in the ghostly pulse of Al-Mahr itself. The drummers' path wound endlessly through North and East, through shadow and fog, their echoes feeding on their own return. Somewhere within that labyrinth of narrow veins, the sound folded back upon itself — a perfect loop of rhythm and ruin. And when the dawn finally came, no one walked those streets, for they said the beat still lingered there, circling without rest, forever calling the sleepers of Al-Mahr to awaken… long after sahur had passed.
Near and Mello have just returned from trick-or-treating. Always trying to outdo each other, they decide to combine their haul and settle things with a game.
The rules are simple:
Both know exactly how much enjoyment (or displeasure) each candy would bring them, as well as how much it would bring the other. They play optimally, each aiming to maximize their own total enjoyment. Being rivals, if multiple moves yield the same personal outcome, they'll choose the one that hurts the other the most.
Output the final total enjoyment of Near and Mello once the game concludes.
The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the number of candies.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^3 \le a_i \le 10^3$$$), where $$$a_i$$$ is the enjoyment Near gains from the $$$i$$$-th candy.
The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$-10^3 \le b_i \le 10^3$$$), where $$$b_i$$$ is the enjoyment Mello gains from the $$$i$$$-th candy.
Two integers — the total enjoyment of Near and Mello after the game.
5 2 4 -3 -3 4 3 -5 2 4 1
10 6
In the sample test case, it can be shown Near will take one, Mello will take two, and Near will take two again, in that order. Thus, Near gets an enjoyment of 4 + 4 + 2 = 10, while Mello gets an enjoyment of 4 + 2 = 6.
As everyone knows, Michael loves food. With Halloween around the corner, he also has bucketfuls of candy that he has been meaning to get rid of. He decided to split up his candy into $$$n$$$ goody-bags and hand them out to some of his friends. He has a total of $$$k$$$ friends, and wants to ensure the following:
As a reminder, $$$\gcd(a,b)$$$ is the greatest positive integer that is a factor of $$$a$$$ and $$$b$$$. The $$$\gcd$$$ of an array $$$A$$$ is the greatest positive integer that is a factor of all numbers in the array $$$A$$$, or:
$$$$$$\gcd(A_1, A_2, \ldots, A_N) = \gcd(\gcd(\ldots(\gcd(A_1, A_2), A_3)\ldots), A_N)$$$$$$
Help Michael find the total number of partitions he can create!
The first line of input contains two integers $$$n$$$ ($$$5 \le n \le 2 \cdot 10^5$$$) and $$$k$$$ ($$$2 \le k \le \min(200, n)$$$), the number of goody-bags and the number of friends Michael is giving candy to.
The second line contains $$$n$$$ integers, where $$$a_n$$$ ($$$1 \le a_n \le 10^9$$$) denotes the number of candies in the $$$n$$$th bag.
Output a single integer, denoting the number of possible partitions. This number may be very large, but Michael wants to add a further spook by avoiding the common modulos. Thus, output your answer under modulo $$$10^9 + 3773 \cdot 263$$$.
In case you're curious, this modulo is also a safe prime, just like $$$10^9 + 7$$$!
5 22 7 3 6 4
3
In the sample, we have the following partitions: