CardDrawGame
SRM 775 · 2020-01-15 · by misof
Problem Statement
You have a deck of cards. Each card has a small nonnegative integer written on it. You are given the
You are playing a game in which the goal is to end with three cards whose total is target. The game is played as follows:
- The deck is randomly shuffled.
- You draw the top three cards.
- You decide which of the three cards in your hand you want to keep and which ones you want to discard. You may keep any subset of cards, including none or all of them.
- You discard the chosen cards onto a separate pile. (The discarded cards do not go back into the deck.)
- You draw more cards from the deck until you have three cards in your hand again.
- If the sum of your cards is target, you win. Otherwise, you lose.
You also lose the game whenever you try to draw a card from an empty deck.
Assuming you play optimally, what is the probability of winning the game?
Notes
- The returned value must be within 1e-9 absolute or relative error of the actual value to be accepted.
Constraints
- target will be between 0 and 50, inclusive.
- count will contain between 1 and 20 elements, inclusive.
- Each element of count will be between 0 and 100, inclusive.
3
{0, 3}
Returns: 1.0
The deck has three cards, each of which is a 1. You're guaranteed to get a total of 3 on the initial draw of 3 cards.
10
{3, 3}
Returns: 0.0
There's six cards in the deck, but none of them are larger than a 1, so getting a total of 10 is impossible.
3
{1, 3}
Returns: 1.0
One of the four cards is a 0 and the other three are 1s. If you draw all three 1s, you win. If you draw two 1s and the 0, the optimal play is to discard the 0 and to draw the remaining card: the third 1.
6
{1, 1, 3}
Returns: 0.7000000000000001
There's a 0.1 chance of getting 2-2-2 on the initial draw, and not needing to draw any cards. There's a 0.3 chance of getting 0-1-2 on the first three cards (in any order), after which redrawing two cards for the 0 and 1 is guaranteed to end up a winning hand. There's a 0.3 chance of getting 0-2-2, and a 0.3 chance of getting 1-2-2; in either case, redrawing one card gives a 0.5 chance of getting the winning hand. Thus, the answer is 0.1 + 0.3 * 1.0 + 0.6 * 0.5 = 0.7
12
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
Returns: 0.003681666273366085
3
{0,0,0,2}
Returns: 0.0
There are only two cards. You will lose the game almost immediately, as you are unable to draw the initial three-card hand.
0
{3, 3}
Returns: 0.39999999999999997
You always want to keep all the 0s you have and discard all the 1s. In particular, if your initial draw is three 1s, the optimal strategy is to discard the whole hand.
Submissions are judged against all 143 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CardDrawGame with a public method double winChance(int target, vector<int> count) · 143 test cases · 2 s / 256 MB per case