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!
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.
The output should consist of a single line containing a single integer, the Cheat Score of the given cheat code.
up up down down left right left right b a start
11
up down up down right left right left a b stop
2
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.
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.
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 "YES" if the house number is a masterpiece, and "NO" otherwise.
801
YES
680
NO
906
YES
123
NO
01
NO
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