Problem Statement
Limak is in a casino. He has a dollars. He wants to have at least b dollars (to be able to buy a Valentine's day present for a girl he likes). He will try to win the missing money by playing games in the casino. He has enough time to play at most k times.
Limak is a simple bear, so he only plays the simplest game. In this game he can bet any non-negative integer amount (not exceeding his current balance). With probability 50% he loses the bet and with probability 50% he gets it back doubled. For example, suppose he has 10 dollars and he bets 3. If he loses, he will have 10-3 = 7 dollars, if he wins, he will have 7+2*3 = 10+3 = 13 dollars.
Limak does not know anything about strategies. Therefore, each time he plays a game, he chooses the amount to bet uniformly at random among all valid bets. For example, if he currently has 5 dollars, in the next game he will bet 0, 1, 2, 3, 4, or 5 dollars, each with probability 1/6.
As soon as he has at least b dollars, he stops playing and leaves the casino. He also leaves the casino after playing k games, regardless of whether he has reached his goal.
Of course, there are different ways to play this sequence of games. An optimal strategy is a strategy that always chooses the amount one should bet in a way that maximizes the probability of reaching Limak's goal. There can be multiple optimal strategies.
You are given the
In other words, compute the probability that to a random observer (who knows Limak's goal but not his way of playing) it will seem that Limak follows an optimal strategy throughout his entire stay in the casino.
Definition
- Class:
- OptimalBetting
- Method:
- findProbability
- Parameters:
- int, int, int
- Returns:
- double
- Method signature:
- double findProbability(int a, int b, int k)
- (be sure your method is public)
Notes
- Your return value must have absolute error smaller than 1e-8.
Constraints
- a and b will be between 1 and 100,000, inclusive.
- a will be smaller than b.
- k will be between 1 and 5, inclusive.
Examples
23
26
1
Returns: 0.875
Limak only has the time for a single round. If he bets 0, 1, or 2, the probability that he reaches his goal is 0%. Otherwise, the probability is 50%: if he wins the bet, he will have at least 26 dollars. Thus, the optimal strategy is to bet any amount that is at least 3 dollars. Limak will choose such an amount with probability 21/24.
7
1000
3
Returns: 1.0
Regardless of the amounts Limak bets, he will never reach his goal. Thus, all strategies are optimal: each of them maximizes the probability of reaching Limak's goal. (Sadly, the maximum probability is zero.)
2
3
2
Returns: 0.8888888888888887
7
8
3
Returns: 0.06785714285714287
10
20
2
Returns: 0.09917355371900842
1234
1567
5
Returns: 0.00861475126753315
50123
87654
5
Returns: 0.02304278352341867
97123
100000
5
Returns: 0.0025653685540053964
32123
100000
5
Returns: 0.03953452021937183
1
2
1
Returns: 0.5
1
2
5
Returns: 0.96875
1
3
1
Returns: 1.0
1
3
2
Returns: 0.41666666666666663
1
3
5
Returns: 0.4942129629629629
2
3
1
Returns: 0.6666666666666666
2
3
3
Returns: 0.23611111111111108
2
3
5
Returns: 0.21817129629629628
1
4
2
Returns: 0.33333333333333337
1
5
2
Returns: 1.0
17
20
5
Returns: 0.030888453482772027
100
123
2
Returns: 0.09770746413456388
18
1000
4
Returns: 1.0
1234
39489
5
Returns: 1.0
1
100000
5
Returns: 1.0
99999
100000
5
Returns: 0.03229052816834028
83580
100000
1
Returns: 0.8035438676254173
77770
100000
3
Returns: 0.04096642105661843
12345
98765
5
Returns: 0.4707229271483132
50000
65536
5
Returns: 0.02044442675953916
1666
100000
5
Returns: 1.0
2000
100000
5
Returns: 1.0
1428
99877
5
Returns: 1.0
87655
87656
5
Returns: 0.03228692395295418
8765
22123
4
Returns: 0.07902056022335334