TopCoder srm 708a SafeBetting
problem
Limak is in a casino. He has b dollars. He wants to have at least c dollars (to be able to buy flowers for a girl he likes). In order to achieve that, he must win the money he’s missing.
The casino allows guests to risk some of their money on bets. Limak can make as many bets as he likes, but he has to make them one after another. Each time Limak makes a bet, he chooses the amount he wants to bet. The amount must be a positive integer. Each bet has two possible outcomes: either Limak loses the money, or he gets it back doubled.
For example, suppose Limak has 20 dollars. If he bets 5, he will be left with 20 - 5 = 15 dollars. If he loses the bet, that is his new total. If he wins the bet, he’ll get back 2*5 = 10 dollars, which will bring his total up to 15 + 10 = 25 dollars.
Limak doesn’t want to lose all his money. More precisely, he wants to make sure that at any moment he will have at least a dollars. He will not make a bet if losing the bet would mean that he will have less than a dollars.
For example, suppose Limak currently has 20 dollars. If a = 15, in the next round Limak can bet 1, 2, 3, 4, or 5 dollars. Note that a bet of 6 dollars is not allowed: if he lost it, he would have 20 - 6 = 14 dollars, which is less than a.
You are given the s a, b, and c. We will assume that Limak follows the rules described above when choosing the amounts to bet. Compute and return the smallest B such that Limak can reach his goal (i.e., have at least c dollars) after making B bets.
