Francesca is compiling a list of her favorite (and least favorite) foods to help with meal planning. She gives an integer rating for each of $$$n$$$ different foods, where a higher rating indicates that Francesca likes the food more. Obviously, Francesca would prefer to prepare foods with a high rating more often and prepare foods with a low rating less often.
Given the list of foods and ratings Francesca has given for each food, figure out Francesca's least favorite food (food with the lowest rating) and her favorite food (food with the highest rating). It is guaranteed that each food rating will be distinct and the same food will not appear multiple times on Francesca's list.
The first line of the input consists of a single integer $$$n$$$ $$$(1 \leq n \leq 50)$$$, giving the number of foods that Francesca has given a rating for. The next $$$n$$$ lines each consist of a single token food name $$$f_i$$$ $$$(1 \leq |f_i| \leq 30)$$$ and a rating $$$r_i$$$ associated with that food $$$(-10^9 \leq r_i \leq 10^9)$$$. $$$f_i$$$ will always consist of only uppercase and lowercase letters.
Output Francesca's least favorite food and favorite food, separated by a space.
3 Sandwiches 23 Sardines -2 Pizza 23984
Sardines Pizza
Lang won first prize at a lottery! Unfortunately, instead of receiving lots of money, he has received a shipment of $$$n$$$ boxes of Cheerios. Obviously, Lang is not going to be able to finish too many boxes of Cheerios, but he does not know what to do with them. He reaches out to his $$$m$$$ friends that are available, and they each come one after another to share Lang's Cheerios. Lang decides to be generous, and gives each friend half of his remaining boxes of Cheerios (rounded up if necessary), in the order they come. He will continue until he either runs out of Cheerios, or he has no more available friends.
Given $$$n$$$, the number of boxes of Cheerios he has, and $$$m$$$, the number of friends he has available, determine how many friends will get Cheerios!
The first line of input contains $$$n (1 \le n \le 10^9)$$$ and $$$m (1 \le m \le 50)$$$, the number of Cheerio boxes and the number of friends Lang has available, respectively.
A single integer, the number of friends that Lang will give Cheerios to.
15 5
4
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