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
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.
5000
5000
Returns: 36.90021846438633
4950
4772
Returns: 191.15589434419024
4446
4525
Returns: 8.13249058054577E-4
4446
4526
Returns: 0.0
0
0
Returns: 0.0
0
5000
Returns: 0.0
5000
0
Returns: 5000.0
1
5000
Returns: 0.0
5000
1
Returns: 4999.00019996
5000
2
Returns: 4998.000399920013
4997
3
Returns: 4994.000600240182
4112
2414
Returns: 1698.9961276212473
4321
2313
Returns: 2008.826383724269
1243
1424
Returns: 0.0
1244
4312
Returns: 0.0
4141
114
Returns: 4027.027562459711
1313
331
Returns: 982.2787778158794
4765
4567
Returns: 209.73511834927416
5000
4999
Returns: 37.605546346158974
4999
4999
Returns: 36.896526342887306
4999
5000
Returns: 36.194890582613674
4950
5000
Returns: 7.767994094275865
4920
4990
Returns: 1.4266549085142939
4917
5000
Returns: 0.002145068517158122
4973
4987
Returns: 27.34304499857498
3415
4311
Returns: 0.0
5000
4774
Returns: 237.03978696760726
2562
3514
Returns: 0.0
1
10
Returns: 0.0
60
3263
Returns: 0.0
1
50
Returns: 0.0