OptimalBetting
SRM 708 · 2016-12-07 · by Errichto
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.
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.
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
Submissions are judged against all 34 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class OptimalBetting with a public method double findProbability(int a, int b, int k) · 34 test cases · 2 s / 256 MB per case