Hey, Better Bettor
Time limit4sMemory limit128 MB
Given a refund rate on final losses and a win chance below half per dollar bet, compute the maximum expected profit over any stopping strategy.
- Level
Hard8 of 10
- Topics
- Probability, Dynamic programming, Math
- Solved
- No attempts yet
Problem
"In the casino, the cardinal rule is to keep them playing and to keep them coming back. The longer they play, the more they lose, and in the end, we get it all."
(from the 1995 film Casino)
Recent recessions have not been kind to entertainment venues, and the gambling industry is no exception. Competition among casinos to attract wealthy players is fierce, and some have started offering especially sweet deals.
One casino makes the following offer: you may gamble as much as you like, and when you stop, if you have ended up down by any amount from where you started, the casino refunds of your losses. If instead you are ahead, you keep all of your winnings. There is no time limit and no money limit, but you can redeem the offer only once.
To keep things simple, assume every bet costs 1 dollar and pays out 2 dollars, so a winning bet nets dollar and a losing bet nets dollar. For example, suppose . If you place 10 bets in total before quitting and only 3 of them pay out, you have staked 10 dollars and received 6, a loss of 4 dollars; the casino refunds 20% of that (0.8 dollars), so your final loss is 3.2 dollars. If 6 of them pay out, you finish 2 dollars ahead.
Given the refund percentage and the per-bet winning probability (as a percentage) , write a program that determines the maximum expected profit you can make at this casino using any betting strategy.
Input
The input consists of a single test case: one line containing the refund percentage and the winning probability , separated by a space. Here and , and both and are given with at most two digits after the decimal point.
Output
Print the maximum expected profit, rounded to exactly six decimal places.