UTPC Contest 01-26-24 Div. 2 (Beginner)
A. Up Up Down Down
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Joanna is interested in video game cheat codes! Her favorite is the famous "Konami Code", which goes "up, up, down, down, left, right, left, right, b, a, start".

Joanna recently came across a Codeforces blog post from the infamous user UTPC_Admin. In the blog post, the mysterious UTPC_Admin describes a cheat code that promises to give the reader a rating of 4,000 on Codeforces, a new world record.

To test whether the cheat code is legit, Joanna has decided to compare it to the Konami Code. To do so, she will go through the cheat code input by input and see if it matches the Konami Code in the respective position. She defines the Cheat Score of a code to be the number of inputs which match the Konami Code in position.

Please help Joanna determine the Cheat Score of UTPC_Admin's cheat code so that she can decide whether it is legit!

Input

The input will consist of exactly 11 strings, each of which will be separated with a space and contain only lowercase English letters. Each string will consist of at most 100 letters.

Output

The output should consist of a single line containing a single integer, the Cheat Score of the given cheat code.

Examples
Input
up up down down left right left right b a start
Output
11
Input
up down up down right left right left a b stop
Output
2
Note

The first sample test case is the Konami Code, so its Cheat Score is 11. In the second sample test case, the first and fourth positions are the only ones that match the Konami Code.

B. Upside Downtown
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the vibrant city of Upside, nestled within its downtown, lies a community with a distinctive tradition – the Upside Downtown. Here, house numbers are not just sequences of digits; they are an art form. The residents take pride in crafting numbers that are not only readable right side up but also readable when rotated $$$180$$$ degrees (viewed upside down).

Specifically, the digits $$$0, 1, 6, 8$$$, and $$$9$$$ can be read in both directions. However, house numbers cannot begin with a $$$0$$$ in any orientation.

A new house is being built in this community and you must determine whether its house number complies with this "Upside-Down House Numbers" tradition. Given a proposed house number, determine if it can be read both right side up and upside down.

Input

The input consists of a single positive integer (possibly containing leading zeroes) $$$N\ (1 \leq N \leq 10^9)$$$ representing the proposed house number.

Output

Output "YES" if the house number is a masterpiece, and "NO" otherwise.

Examples
Input
801
Output
YES
Input
680
Output
NO
Input
906
Output
YES
Input
123
Output
NO
Input
01
Output
NO

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