JOIN
Get Time

   Problem Statement  

 Problem Statement for OptimalBetting

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 ints a, b, and k. Compute the probability that the sequence of Limak's bets will follow an optimal strategy.



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

0)
    
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.
1)
    
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)
    
2
3
2
Returns: 0.8888888888888887
3)
    
7
8
3
Returns: 0.06785714285714287
4)
    
10
20
2
Returns: 0.09917355371900842
5)
    
1234
1567
5
Returns: 0.00861475126753315
6)
    
50123
87654
5
Returns: 0.02304278352341867

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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 708 Round 1 - Division I, Level Three