Problem Statement
You have a deck of cards. Each card has a point value that is a small non-negative integer. For each valid value v, count[v] is the count of cards with value v in your deck.
You will now play a game. In the game you draw cards from the deck at random until you either decide to stop (in which case your score is the total value of the cards you have drawn) or until you draw two cards with the same value (in which case the game ends and your score is zero). A more formal description of the game follows.
At the beginning of the game all cards are in the deck and the deck is shuffled uniformly at random. The game consists of one or more turns. In each turn you make a choice: terminate the game, or draw one more card? If you terminate the game this way, your score is equal to the total value of the cards you hold in your hand. If you choose to draw, you take the top card from the deck and add it to your hand. If you drew a card whose value matches another card in your hand, you lose, the game ends and your score is zero. If there are no more cards left in the deck, you must choose to terminate the game (as you cannot draw).
You are given the
Definition
- Class:
- CardDrawPoints
- Method:
- expectedScore
- Parameters:
- int[]
- Returns:
- double
- Method signature:
- double expectedScore(int[] count)
- (be sure your method is public)
Notes
- The return value must have an absolute or a relative error at most 1e-9.
- By "play the game optimally" we mean that your goal is to maximize your expected score and with that goal in mind you make the optimal decisions when to terminate the game and when to draw one more card.
- You know the exact contents of your deck and you use this knowledge when making decisions.
Constraints
- count will contain between 1 and 16 elements, inclusive.
- Each element of count will be between 0 and 10, inclusive.
Examples
{0, 0}
Returns: 0.0
The deck is empty. In the very first round of the game you must choose to terminate the game (as you cannot draw) and your score is therefore guaranteed to be zero.
{1, 1}
Returns: 1.0
The deck contains one card with value 0 and one card with value 1. One possible optimal strategy is "draw until you get the card with value 1, then stop". With this strategy you are guaranteed the score 1.
{ 1, 1, 1 }
Returns: 3.0
The deck contains a card with value 0, a card with value 1, and a card with value 2. One optimal strategy is "draw all three cards, then stop".
{ 1, 3 }
Returns: 1.0
This deck contains one card with value 0 and three cards with value 1 each. The optimal strategy is to stop as soon as you draw one of the cards worth 1: at that point you have nothing to gain by playing on.
{ 2, 1 }
Returns: 0.6666666666666666
{0, 4, 0, 0, 0, 1}
Returns: 2.4000000000000004
There are four cards worth 1 each, and a single card worth 5. If your first draw is a 5, you should draw one more card (which is guaranteed to be a 1) and then stop. If your first draw is a 1, you have two options: stay safe and take the guaranteed score 1, or risk another draw? If you draw a second card, you can get the 5, but you are risking drawing another 1. It turns out that the latter choice is better: you should risk it and draw a second card. (With probability 1/4 you will draw the 5 and have a final score of 6, with probability 3/4 your final score will be 0.)
{0, 7, 0, 0, 0, 1}
Returns: 1.625
This time there are more cards with value 1. If your first draw is a 1, the risk no longer pays off, terminating the game is better than trying your luck.
{2, 2, 2, 2}
Returns: 2.857142857142857
{10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10}
Returns: 21.19778326713989
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4}
Returns: 22.611280854049866
{10, 0, 0, 10}
Returns: 2.2894736842105265
{7,1,9,5,4,9,4,6,6,1,6,8,8,8,6,6}
Returns: 21.397701943348704
{1,6,5,5,8,9,10,0,9,10,6,2,0,8,4,5}
Returns: 18.589897487388342
{0,7,3,9,10,2,8,10,5,6,2,9,4,8,4,0}
Returns: 18.283807268399627
{2,3,2,1,7,2,3,8,4,10,9,2,8,0,1,7}
Returns: 19.928463223125434
{1,4,7,1,8,4,4,8,3,3,9,4,0,4,0,2}
Returns: 16.923717160027913
{10, 9, 1, 10, 0, 0, 1, 0, 1, 5, 2, 0, 3, 0, 7, 8 }
Returns: 14.597369226639337
{10, 9, 10, 9, 10, 9, 10, 9, 10, 9, 10, 9, 10, 9, 10, 9 }
Returns: 21.1576501503383
{1, 1 }
Returns: 1.0
{0, 7, 0, 0, 0, 1 }
Returns: 1.625
{2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }
Returns: 26.529432775439442
{2, 2, 2, 2, 2 }
Returns: 4.18095238095238
{10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 }
Returns: 21.19778326713989
{0, 1, 1 }
Returns: 3.0
{3, 8, 1, 6, 1, 2, 10, 1, 7, 2, 5, 5, 2, 3, 8, 1 }
Returns: 18.54568478137322
{1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1 }
Returns: 26.119948816233645