RedIsGood
SRM 420 · 2008-10-01 · by misof
Problem Statement
You have a deck that contains R red and B black cards.
You are playing the following game: You shuffle the deck, and then begin dealing the cards one by one. For each red card you flip you get a dollar, and for each black card you flip you have to pay a dollar. At any moment (including the beginning of the game) you are allowed to stop and keep the money you have.
Write a method that will take the
Notes
- During the game, your balance may be negative.
- We assume that each permutation of the cards in the deck is equally likely.
- Your return value must have a relative or absolute error less than 1e-9.
Constraints
- R will be between 0 and 5,000, inclusive.
- B will be between 0 and 5,000, inclusive.
0 7 Returns: 0.0
If all cards are black, the best strategy is not to play at all.
4 0 Returns: 4.0
If all cards are red, the best strategy is to flip them all.
5 1 Returns: 4.166666666666667
The strategy "flip all cards" is guaranteed to earn $4. However, we can do better. If we flipped 5 cards and all of them are red, it makes no sense to flip the final, black card. Therefore if we play optimally the expected gain is more than $4.
2 2 Returns: 0.6666666666666666
An optimal strategy for this case: Flip the first card. If it is red, stop. If it is black, flip the second and the third card. If both are red, stop, otherwise flip the fourth card.
12 4 Returns: 8.324175824175823
This is a game I would surely like to play often.
11 12 Returns: 1.075642825339958
Surprisingly, sometimes there is a good strategy even if the number of red cards is smaller than the number of black cards.
Submissions are judged against all 37 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RedIsGood with a public method double getProfit(int R, int B) · 37 test cases · 2 s / 256 MB per case