Kumar thinks he has perfected his recipe for the best chicken and rice dish in the world, Hyderabadi Chicken Biryani. The weekend is fast approaching and his restaurant will be swarmed with to-go orders soon. In order to get ahead of the rush, he plans on cooking a huge batch of his biryani. His recipe calls for $$$s$$$ tablespoons of spice powder for every $$$t$$$ tablespoons of turmeric he uses. In his pantry, he currently has $$$m$$$ tablespoons of spice powder and $$$n$$$ tablespoons of turmeric. He asks you to figure out the amount of spice powder and turmeric to use such that he can maximize the amount of biryani made while still maintaining his recipe's optimal ratio and using integer amounts of each (if it is not possible for him to maintain the ratio with integer amounts of each, output 0 0).
The first and only line of input will contain $$$4$$$ space-separated integers $$$m, n, s$$$ and $$$t$$$ representing Kumar's starting amount of spice powder, Kumar's starting amount of turmeric, Kumar's wanted amount of spice powder in his optimal ratio, and Kumar's wanted amount of turmeric in his optimal ratio, respectively. All quantities are in tablespoons and it is guaranteed that $$$1 \leq m,n,s,t \leq 2 \cdot 10^{9}$$$.
Output two integers, separated by a space, representing the integer amount of spice powder and the integer amount of turmeric that Kumar can use while maintaining his optimal ratio in order to make the maximum amount of biryani. If he cannot make his optimal ratio from his starting amounts, output 0 0.
90 60 3 2
90 60
1920 1200 32 18
1920 1080
Peter Piper is attending a pizza party with his closest pals, and he is determined to pick the perfect, most optimal piece of pizza. Paris, who purchased the rectangular pizzas, is preparing to cut the most superb pie, topped with both pineapple and pepperoni. Peter pays close attention as she cuts the pan pizza in horizontal and vertical lines across, because he knows that once she is finished cutting, he will have mere moments to locate and snatch up the largest slice.
Help Peter pick out the perfect piece of pizza! Compute the location of the largest pizza slice!
The first line of input will contain four integers, $$$L$$$, $$$W$$$, $$$H$$$, and $$$V$$$. The first two integers $$$L$$$ and $$$W$$$ ($$$1 \leq L, W \leq 10^{9}$$$) represent the length and width of the pan pizza respectively. Then $$$H$$$ and $$$V$$$ denote the number of horizontal and the number of vertical cuts that Paris makes into the pizza respectively, where $$$(1 \leq H \leq min(L, 10^{3}))$$$ and $$$(1 \leq V \leq min(W, 10^{3}))$$$.
The next line of input contains $$$H$$$ integers $$$h_i$$$, where each $$$h_i$$$ ($$$0 \lt h_i \lt L$$$) represents the height coordinate of a horizontal cut. Then the third and last line of input contains $$$V$$$ integers $$$v_i$$$, where each $$$v_i$$$ ($$$0 \lt v_i \lt W$$$) represents the width coordinate of a vertical cut. Note that no two horizontal lines and no two vertical lines will ever overlap.
Find the biggest pizza slice! On one line, output two coordinate pairs specifying the upper-left corner and then the lower-right corner of the perfect piece in the pan. Print the coordinate pairs simply as space-separated integers, listing the vertical coordinate before the horizontal coordinate for each pair.
In the case of a tie between multiple equally-sized pizza slices, Peter will pick the slice closest to top of the pan (0 length) where he is standing, and if there is still a tie after that, then he will pick the slice closest to the left side of the pan (0 width).
15 25 4 7 2 7 4 12 15 19 3 6 8 2 14
8 7 14 12
The diagram below provides a layout of the superb pizza in the sample case after Paris has finished cutting it. The largest slice she cuts turns out to be the piece defined by points ($$$8, 7$$$) and ($$$14, 12$$$) with an area of 30. Note that the piece defined by points ($$$19, 7$$$) and ($$$25, 12$$$) is tied for size but is located further to the right side of the pan than Peter's perfect piece.
Kumar overestimated demand for his Chicken Biryani and has $$$n$$$ packaged, ready-to-eat parcels of biryani leftover. In order to not waste any food, he packs all the remaining food into his truck and sets out to donate them to different food shelters across the city. While packing them, he realizes that $$$n$$$ is too big to represent as a traditional integer but he realizes that he can write $$$n$$$ as $$$a!/b!$$$ for integers $$$a$$$ and $$$b$$$ where $$$a \geq b$$$ (Note: $$$x!$$$ is defined as the product of all positive integers less than or equal to $$$x$$$).
At each food shelter he visits, if he has $$$k$$$ remaining parcels of food, he will choose some integer divisor of $$$k$$$, $$$x$$$, such that $$$x \gt 1$$$ and donate $$$k - \frac{k}{x}$$$ parcels of food to that shelter (so he is left with $$$\frac{k}{x}$$$). When $$$k = 1$$$, he will drive home and save the last parcel for himself.
Kumar wants to donate to as many places as he can, so he wants you to figure out, given $$$n$$$ (the number of parcels he has at the start), what is the maximum number of food shelters he can donate to (once he leaves a place he will never come back to it; assume there are at least as many food shelters as the maximum amount he can reach).
The first line of input contains a single line of input $$$t$$$, representing the number of different values of $$$n$$$ that Kumar wants to know the answer for ($$$1 \leq t \leq 10^{6}$$$).
Then, $$$t$$$ lines of input follow with each line containing two space-separated integers $$$a$$$ and $$$b$$$ ($$$1 \leq b \leq a \leq 5 \cdot 10^{6}$$$) where $$$n = a!/b!$$$.
Note: Due to the size of the input, regular Python Input/Output functions may be too slow for this problem.
For each of the $$$t$$$ test cases, output a single line containing a single integer representing the maximum number of food shelters that Kumar could donate to for that value of $$$n$$$.
1 3 1
2
2 6 3 100 21
5 201
Norman loves N&N's, a delicious chocolate-coated candy made by Nars, Inc. that comes in bags. Unfortunately, the factory that the N&Ns are made in is unreliable and fills the bags somewhat haphazardly. Nevertheless, Norman, being an avid fan of the N&N series of chocolates has discovered that there is an underlying distribution to the number of chocolates filled into each bag.
Norman has enough money to buy just one bag of N&N's. However, if he notices his bag has too few N&N's, he can return it to the store for a full refund and get a fresh bag, up to $$$k$$$ times due to Nars policy. Norman can immediately know how many there are in a bag just by holding one in his hand.
How many N&N's can Norman expect to get, assuming he returns bags optimally?
The first line contains $$$n$$$ and $$$k$$$, separated by a space, where $$$n$$$ is the number of distinct amounts of N&N's that a bag can have, $$$k$$$ is the number of times he can return a bag, $$$1 \le n \le 10^5, 0 \le k \le 10^4$$$.
The next line contains $$$n$$$ distinct space-separated integers $$$a_i$$$ where each of the $$$a_i$$$ are a possible number of N&N's the factory produces, and $$$0\le a_i \le 10^6$$$.
The next line contains $$$n$$$ space-separated numbers $$$p_i$$$ so that the probability the factory produces a bag with $$$a_i$$$ N&N's is $$$p_i$$$. $$$0 \lt p_i \lt 1$$$, and $$$\sum_i p_i = 1$$$.
Output a single line, containing the expected number of N&N's Norman can get if he returns bags optimally. Your answer will be correct if it is within $$$10^{-6}$$$ of the correct answer.
3 0 1 3 2 0.4 3e-1 0.3
1.9
3 2 1 3 2 0.4 0.3 0.3
2.482
Your guests are not committed to a standardised order of sandwich assembly, and that makes it difficult to know which order to place each of the $$$n$$$ ingredients in on the sandwich bar. You have lots of other food related things to do, so you decide to just place the ingredients down according to your own preference, at arbitrary distinct locations on your table top. Now your guests will have to travel back and forth along the table placing ingredients in their preferred order.
Supposing that order preferences are indeed uniformly random amongst your guests (that is, each permutation of ingredients is equally likely to be the preference), and given the positions of each of the locations of the ingredients in the order you like in meters, what is the expected time a guest takes to assemble a sandwich? Each guest travels at one meter per second. Answer in seconds.
Each guest begins at the leftmost end of the table, at position $$$0$$$, and exits the sandwich bar at the rightmost end, position $$$W$$$, where $$$W$$$ is the width of the table. Each guest takes every ingredient in exactly the order they prefer.
The first line contains two numbers $$$n, W$$$ with $$$1\le W\le 10^5$$$ and $$$1\le n \lt \min\{10^5, W\}$$$, respectively, the number of sandwich ingredients and the width of the table.
The second line contains $$$n$$$ distinct integers $$$a_1, a_2,\cdots, a_n$$$ with $$$0 \lt a_i \lt W$$$ for each $$$i$$$. $$$a_i$$$ is the location in meters of the ingredient that you personally like to place at the $$$i$$$th position of your sandwiches.
Every guest travels at $$$1$$$ meter per second.
Output a single number that is the expected time in seconds for a random guest to collect the ingredients of their sandwich in the order they desire.
3 4 2 3 1
6.66666666666667
3 12 6 7 5
14.6666666666667
Butchering Farmer John's cows always yields great short ribs, but Old MacDonald (the co-owner of FJ's farm) has found a way to bring their flavor to even greater heights! Each of FJ's cows produces short ribs of a particular type, which is represented by some natural number. It turns out that pairing short ribs taken from different cows with short rib types that share no common factors other than $$$1$$$ creates a sublime contrast in flavor.
Old MacDonald wants to count the number of pairs of cows that can be used in the pursuit of his ideal short rib plate. Can you help him?
The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 100000$$$), the number of cows on the farm. The second line of input contains $$$N$$$ space separated integers $$$x_i$$$, where $$$x_i$$$ ($$$1 \leq x_i \leq 1000000$$$) is the rib type of the $$$i$$$-th cow.
Output a single integer representing the number of optimal short rib pairings by Old MacDonald's standards.
8 1 2 3 4 5 6 7 8
21
After giving out many of his Cheerio boxes, Lang realizes he still has $$$n$$$ cereal boxes left. Feeling great about his philanthropic endeavors, he now decides to play with his cereal boxes. Lang decides to line up his boxes in a straight line (let this line be the x-axis), with each cereal box being located at some $$$(x_i, 0)$$$. Furthermore, Lang's cereal boxes each have an individual height of $$$h_i$$$ as well.
Looking at the cereal boxes, Lang quickly uses his mastery of physics to calculate the exact probability $$$p_i$$$ that when tapped that the box will fall left. As such, the $$$i^{th}$$$ cereal box would also fall right with probability $$$1 - p_i$$$. Note that since some cereal boxes, when they fall over, would actually cause a chain reaction, and knock down more boxes, which could then go on to knock down more boxes. Specifically, if a box has height $$$h$$$, then any box within a distance of $$$h$$$ or less and in the same direction that the original box fell in would also fall in that direction. These boxes can continue to cause more boxes to fall.
Lang himself is interested in the minimum number of taps it will take for all the boxes to one side of his current direction, namely $$$(0, 0)$$$, to fall. Since he has a very large number of boxes, this task proves to very difficult for him. As such, he decides to utilize a heuristic to weight his choice with regards to the probability of the boxes on two ends of his current position falling outwards. Specifically, if at a certain point, if the next box on the left has a probability $$$p_i$$$ of falling left, and the next box on the right has a probability $$$p_j$$$ of falling left, then he will choose the book on the left with probability $$$\frac{p_i}{p_i + (1 - p_j)}$$$.
While this heuristic is clearly suboptimal, it does make Lang's actions strictly probabilistic. Given this information, determine the probability that Lang will knock over all Cheerio boxes to his left before all his Cheerio boxes on the right. If it happens to be that after a tap, the leftmost box and the rightmost box both fall without any additional taps, this will still count.
The first line of the input is a single integer, $$$n (1 \le n \le 10^3)$$$, the number of boxes.
The next $$$n$$$ lines of input each contain 2 integers $$$x_i (-10^8 \le x_i \le 10^8)$$$ and $$$h_i (1 \le h \le 10^5)$$$ followed by a real number $$$p_i (0 \le p \le 1.0)$$$, where $$$x_i$$$ is the coordinate the box is at on the x-axis, $$$h_i$$$ is the height of the box, and $$$p_i$$$ is the probability that the box falls left.
It is guaranteed there is at least one box to both the left and the right of where Lang starts and that there is no box where Lang starts.
A single real number, the probability that all cereal boxes on the left fall before the ones on the right, or if they all fall after the same tap.
The answer will be judged as correct if it has absolute or relative error at most $$$10^{-4}$$$.
4 -4 2 0.75 -2 2 0.75 2 2 0.5 4 2 0.5
0.6660000000999999
Calculation for sample testcase detailed below, with overall success rate of each path in parenthesis.
Pick left, fall left: $$$0.6 \cdot 0.75 (0.45)$$$
Pick left, fall right: $$$0.6 \cdot 0.25$$$
Pick right, fall left, pick left: $$$0.4 \cdot 0.5 \cdot 0.6$$$
Overall chance: $$$0.45 + 0.09 + 0.018 + 0.09 + 0.018 = 0.666$$$
Chang has received a request to decorate an enormous amount of cupcakes for an upcoming wedding reception. The bride and groom are both programmers, so he decides to theme his frosting around balanced parentheses sequences. We can define balanced parentheses sequences as follows:
The planned arrangement of Chang's cupcakes is a line of frosted opening and closing parentheses (one symbol per cupcake) such that the created bracket sequence is balanced. Although the cupcakes are already baked, Chang does not have time to frost all the cupcakes by himself before the wedding due to prior commitments. Chen, his eager assistant, offers to frost a prefix of the cupcakes and create instructions for the rest of the cupcakes for Chang to frost upon returning.
Unfortunately, Chen forgot to leave Chang the intended finished sequence, and it is the day of the wedding! Chang does not perform well with indecision, and wants to know the number of different ways he can finish frosting the remaining cupcakes with $$$($$$ and $$$)$$$ such that a balanced bracket sequence is still created. Help Chang calculate the number of options he has for finishing frosting the cupcakes!
The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^6$$$), the total number of cupcakes. The second line of input contains a string $$$s$$$ of left and right parentheses representing the prefix of cupcakes already frosted. This prefix has length at most $$$N$$$ and is not an empty string.
Output a single integer representing the number of ways Chang can frost the remaining cupcakes modulo $$$10^9+7$$$.
6 (()
2
4 ((
1
Vicki is eating a sandwich from Vivian's Verbose sandViches. Vivian's sandViches are known for their distinctive lettering: each sandwich comes with a string printed on the top. Vicki has a special way of eating sandViches. She first finds a prefix of the remaining sandVich she has that is a palindrome, and then eats, in one bite, the first half (rounded up) of that palindrome. How many bites does it take Vicki to eat the whole sandwich?
In particular, if the string remaining on her sandVich is $$$s$$$ with characters $$$s_0, s_1, \dots s_n$$$, Vicki identifies some $$$k$$$ such that $$$s_i = s_{k-i}$$$ for $$$0\le i \le k$$$ and bites off $$$s_0, s_1, \dots, s_{\lfloor k/2\rfloor}$$$
A single line containing the string on the sandwich $$$s$$$, where the length of the string is less than $$$10^5$$$.
A single line containing the smallest number of bites required to finish the sandwich
aba
2
ceecd
4
For the first sample input, the first bite Vicki could take could be $$$ab$$$, leaving the sandVich with just $$$a$$$, and then eat the last letter in one bite, for a total of two bites.
For the second, Vicki could eat $$$ce$$$, and then eat each of the last letters individually for a total of $$$4$$$ bites.