In the city of Wonkville, inside the world-famous chocolate factory is a lottery system called the Upside-Down Chocolate Room. Here, delightful treats are hidden behind a series of magical upside-down slot machines. Contestants who may enter the room follow a curious tradition: instead of pulling levers downward, they prefer to pull them upwards!
As a contestant in the Chocolate Room, you are given a set of $$$k$$$ slot machines, each with an associated reward distribution. Each slot machine $$$i$$$ generates rewards according to a known finite, discrete probability distribution $$$P_i$$$. You have a total of $$$n$$$ pulls to distribute among the $$$k$$$ slot machines. Your task is to maximize your expected winnings after these $$$n$$$ pulls. After $$$n$$$ pulls, what is the value of your expected winnings?
The first line contains two integers $$$n$$$ and $$$k$$$ for $$$1 \leq n,k \leq 100$$$.
The following $$$3k$$$ lines contain three separate lines for each slot machine $$$1 \leq i \leq k$$$:
Please determine the maximum expected winnings from $$$k$$$ slot machines after $$$n$$$ pulls.
Your answer will be considered correct if its absolute or relative error doesn't exceed $$$10^{−6}$$$.
5 351 3 9 7 30.15 0.4 0.1 0.2 0.1528 70.5 0.531 2 30.25 0.30 0.45
37.5
The world has turned upside down!
In this reversal of roles, we need your help to write a problem!
The problem goes like this: I start with the number 1. Then, I can apply a sequence of operations, where an operation is just multiplying my current number by any positive integer $$$k$$$. For example, I can select $$$k = 3$$$, acquiring the number $$$1 \times 3 = 3$$$. Then I can select a new $$$k = 4$$$, acquiring the number $$$3 \times 4 = 12$$$. Then I select $$$k = 2$$$, acquiring the number $$$12 \times 2 = 24$$$. This results in the sequence of numbers $$$[1, 3, 12, 24]$$$.
My boss (Bennett) has provided me with a list of $$$N$$$ of his favorite numbers; for my problem, I need to find sequences that contain as many of his favorite numbers as possible.
If I create the perfect sequence, how many of Bennett's favorite numbers can I include?
The first line contains a single integer $$$N\ (1 \le N \le 10^3)$$$, denoting the number of Bennett's favorite numbers.
The second line contains $$$N$$$ integers $$$a_1,...,a_N$$$ ($$$1 \le a_i \le 10^{18}$$$), representing the $$$N$$$ target numbers. All $$$a_i$$$ are guaranteed to be distinct.
Output a single integer, the maximum number of favorite numbers you can acquire in a single sequence.
42 6 10 12
3
One possible sequence is $$$[1, 2, 6, 12]$$$, which attains 3 of Bennett's favorite numbers.
Uptown is hosting their annual Downside-Up dance, where they invite their antipodal neighbors from Downside to participate in a celebration of Up-Down harmony. The dance commences as follows:
The Uptownites and the Downsiders line up in a row in some order. Next, a consecutive segment of people is chosen to participate in the dance. In the spirit of intermingling, each person must be able to pair up with someone from the other city. That is to say, the segment chosen must contain the same number of Uptownites and Downsiders.
The dance organizers want this year's dance to be as big as possible. Given the orders that the Uptownites and Downsiders have lined up in, can you help them determine the longest segment of people they can choose to participate in the dance for each one?
The first line of the input contains a single integer $$$t$$$ $$$(1\leq t\leq 10^4)$$$ — the number of test cases. This is followed by the descriptions of the test cases.
The first line of each test case contains an integer $$$n$$$ $$$(1\leq n\leq 2\cdot 10^5)$$$, the number of people that are lined up.
The second line of each test case contains a string of length $$$n$$$ consisting of the characters U and D, denoting the city each person belongs to, with U representing an Uptownite and D representing a Downsider.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.
For each test case, output a single integer — the length of the longest consecutive segment containing the same number of Uptownites and Downsiders that can be chosen from the given ordering.
44UDUD7UUUDDDD10DDUDDUDUUD2DD
4 6 8 0
In the first test case, we can take all the people. Uptownites and Downsiders rejoice!
In the second test case, we can take the segment spanning from the first person to the sixth person.
In the third test case, we can take the segment spanning from the second person to the ninth person.
In the fourth test case, there are no Uptownites, so we cannot choose a segment of positive length at all.
Dhomas owns a disco club in downtown Daustin. His dance floor is an $$$N \times M$$$ grid of illuminated tiles, and there is a person standing on each tile. Dhomas designed the dance floor with a unique quirk. Dhomas can select a tile at $$$(\text{row} = R, \text{column} = C)$$$ and reverse the direction of gravity for all tiles at position $$$(\text{row} = i, \text{column} = j)$$$ where $$$i \leq R$$$ and $$$j \leq C$$$. Dhomas defines this entire process as one "reversal" on the dance floor. If the person on such a tile is standing right-side up initially, they will be flipped upside down. Likewise, if they are upside down, they will be flipped right-side up.
As the disco club is coming to a close for the night, Dhomas needs to flip everyone on the dance floor back to the right-side up position before they leave. Dhomas wants to do this quickly so he asks you to find the minimum number of reversals required to flip everyone on the dance floor right-side up.
The first line of input contains two space-separated integers $$$N, M\ (1 \leq N, M \leq 3000) - $$$ the vertical and horizontal dimensions of the dance floor.
The next $$$N$$$ lines each contain $$$M$$$ integers. The integer at $$$(\text{line} = i, \text{column} = j)$$$ indicates that the person standing on tile $$$(i,j)$$$ is initially either upside down $$$(1)$$$ or right-side up $$$(0)$$$.
Output one integer, the minimum number of reversals needed to flip everyone on the dance floor right-side up (reset the entire grid to $$$0$$$s).
2 21000
1
2 3110100
3
5 711010011101001110100111110111111111
7
Today is Dinnerbone's birthday! For their birthday present, Grumm (Dinnerbone's best friend) decides to gift Dinnerbone an array $$$A$$$ of length $$$N\ (1\leq N \leq 15)$$$. This array is very special to Dinnerbone because each $$$\lvert{A_i}\rvert\leq 10^{4}$$$. Given that Dinnerbone can select any strict subset $$$S$$$ of the array, calculate the maximum and minimum possible values of $$$$$$\left(|S|\cdot (-1)^{|S|}\cdot \sum_{x \in S} x^3\right)$$$$$$
The first line contains $$$T\ (1\leq T\leq 1000)$$$, the number of test cases.
Each test case will start with $$$N\ (1\leq N \leq 15)$$$, the length of the array. The next line contains an array $$$A$$$ of length $$$N$$$, where the $$$i$$$-th element is $$$A_i$$$.
For each case, print the minimum and maximum value, separated by a space and ending with a newline.
15-14 12 -11 8 8
-12204 10689
Alex enjoys playing a card game, Australian Solitaire. This game involves a special deck of playing cards, with 4 Aces and 100 of every other denomination (Kings, Queens, ... 2s). There are no suits in this deck. In Australian Solitaire, the player places $$$N$$$ $$$(1 \leq N \leq 20)$$$ cards in a line, without replacement.
A sequence of cards is considered $$$upside-down$$$ if it meets the following criteria:
1. The first card can be any rank.
2. The rank of any subsequent card must either be strictly greater than the rank of the previous card, OR an Ace.
The rank of the cards from smallest to largest is Ace, 2, 3, … King. How many $$$upside-down$$$ sequences of $$$N$$$ cards are there? Two sequences are considered the same if for each card in the sequence, the denomination/rank of the card is the same.
Output your answer mod $$$10^9 + 7$$$.
The input contains a single integer, $$$N$$$.
Please output the number of upside-down sequences of length $$$N$$$.
2
91
This is an interactive problem.
For her friend Bob's birthday, Alice is baking him his favorite dessert, pineapple upside down cake!
Alice allows Bob to make a series of at most 50 queries. In the $$$j^\text{th}$$$ query, Bob is allowed to send Alice a positive integer $$$q_j$$$. In response, Alice will tell Bob $$$s_{((q_j - 1) \text{ mod } N) + 1}$$$ (informally, Bob learns the $$$q_j^\text{th}$$$ sweetness value, wrapping around if $$$q_j$$$ is larger than $$$N$$$). After asking his series of queries, Bob's goal is to guess the value of $$$N$$$.
Bob has been having trouble with this daunting task, but he still wants to learn $$$N$$$ so that Alice will reward him with his birthday cake. Please assist him!
You are allowed to make at most 50 queries by printing a line containing "? q" $$$(1 \leq q \leq 2 \cdot 10^9)$$$ (without quotes). In return, you may read in a single integer representing $$$s_{((q - 1) \text{ mod } N) + 1}$$$. When you are prepared to guess the value of $$$N$$$, print a single line "! x" $$$(1 \leq x \leq 2 \cdot 10^5)$$$ (without quotes), where $$$x$$$ represents the guess for the value of $$$N$$$, and then exit.
After printing each query (including your final guess) you will need to flush the output stream, because it is possible that some part of your output is left in the buffer. For example, you can use fflush(stdout) in C++, System.out.flush() in Java, flush(output) in Pascal and stdout.flush() in Python. Otherwise, you may get the verdict Idleness limit exceeded.
Exit immediately after receiving -1 and you will see a Wrong answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.
? 1 ? 2 ? 3 ? 4 ! 3
1 2 5
The sample test shows an example of interaction in the case where $$$N = 3, s_1 = 1, s_2 = 2$$$, and $$$s_3 = 5$$$. The first three queries yield the values of $$$s_1, s_2$$$, and $$$s_3$$$, and the fourth query yields the value of $$$s_{(3 \text{ mod } 3) + 1} = s_1$$$.
It's a lazy Friday evening, perfect time to throw some shrimps on the barbie!
Luca has an infinite number of shrimp, and he plans to cook some on his barbecue grill. Luca's grill can be represented as an $$$n\times m$$$ grid of squares, where each square can hold up to one shrimp. However, due to his grill being of the upside-down variety, it has a unique quirk. If any $$$2\times 2$$$ subgrid of squares contains an odd number of shrimp, then all the shrimp in the subgrid will burn!
Luca was wondering how much this quirk affects his ability to cook and wanted to know the number of ways he could place shrimp on the grill that could result in them burning. However, Luca has to get back to grilling his shrimps, so he doesn't have any more time to spend thinking about this problem. You, on the other hand, have plenty of time. Please help Luca count the number of ways to place shrimp on the grill such that at least one shrimp will burn. Since this number could be large, output it modulo $$$998244353$$$.
The input contains two integers $$$n$$$ and $$$m$$$ $$$(2\leq n, m\leq 2000)$$$ — the dimensions of the barbecue grill.
Output a single integer, the number of ways to place shrimp on the grill that could result in a shrimp burning, modulo $$$998244353$$$.
2 2
8
2 3
48
5 8
444591027
For the first test case, the 8 possible ways are:

where a 1 represents a shrimp and a 0 represents an empty square.