AnyNumber
SRM 700 · 2016-10-02 · by lg5293
Problem Statement
You just made it to the final round of a game show! You now need to play a game to win your prize.
You have been given some cards.
Each card contains a string of digits.
You are given these strings of digits in the
On the podium in front of you there is a large board.
The board is divided into rows.
Each row contains some number of consecutive blank slots.
Different rows may contain a different number of slots.
You are given the
The game is played in turns. In each turn you choose one of the cards you have. Then, one of the slots that are still blank is chosen uniformly at random. Finally, the chosen card is placed onto the chosen slot. All random choices are mutually independent.
The game ends as soon as one of the rows becomes completely filled. The amount you win is the number obtained by reading the filled row from the left to the right. (I.e., you can obtain your prize by concatenating the strings of digits on the cards that were placed into the filled row, in the order in which they now appear in the filled row. Note that this order may be different from the order in which those cards were played during the game.)
You have no idea how to play this game.
Therefore, you decided to simply play your cards in the order in which they are given in the
We are interested in the expected value of your prize. Let M = 1,000,000,007. It can be shown that the exact expected value of your prize is a rational number. Let P and Q be relatively prime nonnegative integers such that the expected value of your prize is P/Q. It can be shown that Q and M are relatively prime. Compute and return the value (P * Q^(-1)) modulo M, where Q^(-1) is the inverse element to Q modulo M.
Constraints
- n will be between 1 and 50, inclusive.
- cards will have exactly n elements.
- Each element of cards will contain only characters between '0' and '9', inclusive.
- Each element of cards will have between 1 and 50 characters, inclusive.
- m will be between 1 and n, inclusive.
- blank will have exactly m elements.
- The sum of all elements in blank will be less than or equal to n+m-1.
- Each element of blank will be between 1 and n, inclusive.
{"1000000007"}
{1}
Returns: 0
You have a single card. The card contains the string "1000000007". The board contains a single row with a single blank slot. In the only round of the game you play the card, the slot gets chosen, and the game ends because you just filled a row completely. Your prize is 1000000007. This prize can be written as 1000000007/1. Hence, we have P=1000000007, Q=1, and therefore the correct return value is (P * Q^(-1)) modulo M = (1000000007 * 1) modulo 1000000007 = 0.
{"123", "45", "6", "7"}
{3}
Returns: 401988
You have four cards. The board contains a single row with three consecutive blank slots. As you play the game, the cards with "123", "45", and "6" will be placed into that row, each onto a randomly chosen blank slot. This means that there are six equally likely prizes: 123456, 123645, 451236, 456123, 612345, and 645123. The expected value of your prize is their average: 401988. The correct return value is (401988 * 1^(-1)) modulo M = 401988.
{"46", "135", "00000", "3024920394"}
{1,2}
Returns: 166676675
This time the board contains two rows: one with 1 blank slot, the other with 2 blank slots. Here are the possible outcomes of this game: With probability 1/3 you will win the game immediately after playing the first card. (This happens if it gets played onto the blank slot in the first row.) In this case your prize is 46. With probability 1/3 your prize will be 135. This happens whenever the first card goes into the second row and then the second card goes into the first row. With probability 1/6 your prize will be 46135. With probability 1/6 your prize will be 13546. Thus, the expected value of your prize is 60043/6. The correct return value is (60043 * 6^(-1)) mod (10^9 + 7) = (60043 * 166666668) mod (10^9 + 7) = 166676675.
{"0001","1"}
{2}
Returns: 5006
Your prize is either 10001 or 11. Note that unnecessary leading zeros do not change the value of a number.
{
"23049823728915788877792227159747104412489500114823",
"0","0","0","0","0","0","0","0","0","0","0","0","0","0"
}
{1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 700700700
Submissions are judged against all 136 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AnyNumber with a public method int findExpectation(vector<string> cards, vector<int> blank) · 136 test cases · 2 s / 256 MB per case