RedIsGood | Topcoder Archive

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 ints R and B, and return the expected amount you will gain if you play this game optimally.

Definition

Class:: RedIsGood
Method:: getProfit
Parameters:: int, int
Returns:: double
Method signature:: double getProfit(int R, int B)
(be sure your method is public)

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.

Examples

```
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.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.