RockPaperScissorsMagicEasy
SRM 653 · 2015-01-29 · by dreamoon
Problem Statement
Alice and Bob are going to play a variant of the traditional rock-paper-scissors game. Their game is played using cards. Each card shows one of the three pictures: a rock, a paper, or scissors. There is a sufficient supply of cards of each type. Bob has already chosen a sequence of cards and he has arranged them into a row, face down. It is now Alice's turn to do the same. Once she does that, they will use the two sequences of cards to play the game: For each i, Alice's i-th card and Bob's i-th card will be revealed and compared using the standard rules of rock-paper-scissors. Whenever Alice's card wins, Alice gets a point. Alice gets no points for a loss or a tie.
Alice has marked Bob's cards, so now she can tell which card has which symbol on it.
You are given this information as a
You are also given an
Let X be the number of sequences in which Alice can play her cards if she wants to achieve exactly score points. Return the value (X modulo 1,000,000,007).
Constraints
- The number of elements in card will be between 1 and 2,000, inclusive.
- All elements of card will be between 0 and 2, inclusive.
- score will be between 0 and 2,000, inclusive.
{0,1,2}
2
Returns: 6
Bob has played his cards in the order rock-paper-scissors. Alice wants to score 2 points. Hence, she must win twice, and lose to Bob or tie him once. One possible way in which she can play her cards is paper-scissors-scissors: her paper beats Bob's rock (1 point), scissors beat paper (1 point), and scissors tie with scissors (0 points). There are five other ways how Alice can score 2 points: paper-scissors-paper, paper-paper-rock, paper-rock-rock, rock-scissors-rock, and scissors-scissors-rock.
{1,2}
0
Returns: 4
{2,2,1,0,0}
10
Returns: 0
{0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2}
7
Returns: 286226628
{0,1,2,0,1,2,2,1,0}
8
Returns: 18
Submissions are judged against all 80 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RockPaperScissorsMagicEasy with a public method int count(vector<int> card, int score) · 80 test cases · 2 s / 256 MB per case