UTPC Contest 01-26-24 Div. 1 (Advanced)
C. Gambler's Chocolate Cove
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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?

Input

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$$$:

  • the number of elements $$$1 \leq m_i \leq 1000$$$ in $$$R_i$$$ and $$$P_i$$$, for all $$$1\leq i\leq k$$$
  • the reward distribution $$$R_i$$$ as $$$m_i$$$ space-separated distinct integers $$$r_1\: r_2\: ... \: r_{m_i}$$$ for $$$0\leq r_i\leq 100$$$ followed by
  • the probability distribution $$$P_i$$$ as $$$m_i$$$ space-separated real values $$$p_1 \: p_2\: ... \: p_{m_i}$$$ for $$$0 \leq p_i \leq 1$$$ with up to 8 digits after the decimal point. It is guaranteed that $$$p_1+ p_2+ ... + p_{m_i}=1$$$.
Output

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}$$$.

Example
Input
5 3
5
1 3 9 7 3
0.15 0.4 0.1 0.2 0.15
2
8 7
0.5 0.5
3
1 2 3
0.25 0.30 0.45
Output
37.5

D. The World Turned Upside Down
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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?

Input

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

Output a single integer, the maximum number of favorite numbers you can acquire in a single sequence.

Example
Input
4
2 6 10 12
Output
3
Note

One possible sequence is $$$[1, 2, 6, 12]$$$, which attains 3 of Bennett's favorite numbers.

E. Up Down Matching
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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?

Input

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$$$.

Output

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.

Example
Input
4
4
UDUD
7
UUUDDDD
10
DDUDDUDUUD
2
DD
Output
4
6
8
0
Note

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.

F. Down Up Disco
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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

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).

Examples
Input
2 2
10
00
Output
1
Input
2 3
110
100
Output
3
Input
5 7
1101001
1101001
1101001
1111011
1111111
Output
7

G. Dinnerbone and Array
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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)$$$$$$

Input

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$$$.

Output

For each case, print the minimum and maximum value, separated by a space and ending with a newline.

Example
Input
1
5
-14 12 -11 8 8
Output
-12204 10689

H. Australian Solitaire
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$.

Input

The input contains a single integer, $$$N$$$.

Output

Please output the number of upside-down sequences of length $$$N$$$.

Example
Input
2
Output
91

I. Pineapple Upside Down Cake
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

For her friend Bob's birthday, Alice is baking him his favorite dessert, pineapple upside down cake!

Even more exciting, Alice has prepared a guessing game for Bob! Alice has placed a secret number of cherries on top of the cake, denoted by a positive integer $$$N\ (1 \leq N \leq 2 \cdot 10^5)$$$. The cherries are in a circle around the edge of the cake, and each cherry has a sweetness value. The $$$i^\text{th}$$$ cherry in the circle has sweetness $$$s_i\ (1 \leq s_i \leq 2 \cdot 10^9)$$$, and in fact it is guaranteed that $$$s_1 \lt s_2 \lt \dots \lt s_N$$$, though these values are also unknown to Bob (he only knows that they are strictly increasing).

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!

Interaction

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.

Example
Input
? 1

? 2

? 3

? 4

! 3
Output

1

2

5
Note

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$$$.

J. Careful Cookout
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$.

Input

The input contains two integers $$$n$$$ and $$$m$$$ $$$(2\leq n, m\leq 2000)$$$ — the dimensions of the barbecue grill.

Output

Output a single integer, the number of ways to place shrimp on the grill that could result in a shrimp burning, modulo $$$998244353$$$.

Examples
Input
2 2
Output
8
Input
2 3
Output
48
Input
5 8
Output
444591027
Note

For the first test case, the 8 possible ways are:

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