Problem Statement
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
Definition
- Class:
- SafeBetting
- Method:
- minRounds
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int minRounds(int a, int b, int c)
- (be sure your method is public)
Constraints
- a, b and c will each be between 1 and 1000, inclusive.
- a will be smaller than b.
- b will be smaller than c.
Examples
15
20
48
Returns: 3
Limak has 20 dollars. He wants to have at least 48 dollars. He can never have less than 15 dollars. In the first round Limak can bet at most 5 dollars (as explained in the example in the problem statement). If he bets 5 and wins, he will have 25 dollars. In the second round he will be able to bet at most 10 dollars. If he wins that round as well, he will have 35 dollars. Finally, it is possible that in the third round Limak will bet 13 dollars and he will win the bet. At that moment he will have exactly 48 dollars. The correct return value is 3, because Limak needed to place at least 3 bets. He cannot reach 48 dollars by placing fewer than 3 bets.
10
400
560
Returns: 1
5
7
21
Returns: 3
5
7
22
Returns: 4
17
30
1000
Returns: 7
1
2
3
Returns: 1
1
2
4
Returns: 2
5
17
80
Returns: 3
17
20
21
Returns: 1
17
20
23
Returns: 1
17
20
24
Returns: 2
17
20
26
Returns: 2
17
20
27
Returns: 2
1
2
1000
Returns: 10
1
2
999
Returns: 10
1
999
1000
Returns: 1
1
998
1000
Returns: 1
1
100
1000
Returns: 4
100
116
131
Returns: 1
100
116
132
Returns: 1
100
116
133
Returns: 2
123
150
1000
Returns: 6
57
157
257
Returns: 1
123
124
987
Returns: 10
5
12
453
Returns: 6
5
12
452
Returns: 6
998
999
1000
Returns: 1
987
988
1000
Returns: 4
987
999
1000
Returns: 1
900
960
1000
Returns: 1
900
915
1000
Returns: 3
15
20
30
Returns: 2
2
3
4
Returns: 1
19
20
22
Returns: 2
15
20
789
Returns: 8
2
4
8
Returns: 2