Problem Statement
You are thinking of using the following betting strategy: in the first round, you bet one dollar. If you win the bet, you win the dollar and bet another dollar in the next round. Otherwise you lose the dollar and bet two dollars in the second round (provided you still have at least two dollars in your account). If you win, you get the two dollars and bet one dollar in the third round, otherwise you lose the two dollars and bet four dollars in the third round (provided you have at least that amount in your account) and so on. In other words, whenever you lose a bet, you double the value of the bet for the next round. If you don't have enough money to cover your bet, you have to stop betting. Whenever you win, the bet for the next round will be one dollar.
For example, if you start with 10 dollars, and you win the bet in the first round, lose the bet in the next two rounds and then win the bet in the fourth round, you will end up with 10+1-1-2+4 = 12 dollars.
You will be given four
Definition
- Class:
- TestBettingStrategy
- Method:
- winProbability
- Parameters:
- int, int, int, int
- Returns:
- double
- Method signature:
- double winProbability(int initSum, int goalSum, int rounds, int prob)
- (be sure your method is public)
Notes
- The returned value must have an absolute or relative error less than 1e-9.
Constraints
- initSum will be between 1 and 1,000, inclusive.
- goalSum will be between (initSum + 1) and 1,000, inclusive.
- rounds will be between 1 and 50, inclusive.
- prob will be between 0 and 100, inclusive.
Examples
10
11
4
50
Returns: 0.875
You have a 50% chance of reaching 11 dollars in the first round. You could also win by losing the first round and winning the second, with a 25% chance, or losing the first two rounds and winning the third one, with a 12.5% chance. Note that the fourth round is never needed. If you lose the first three rounds, you can't cover your fourth bet. In any other case, you will have already reached 11 dollars and stopped.
10
20
20
50
Returns: 0.3441343307495117
10
20
10
90
Returns: 0.34867844010000015
You have to win every round. Since the probability of winning a round is pretty high, you have a decent chance of doing this.
96
97
1
79
Returns: 0.79
62
63
1
65
Returns: 0.65
68
69
2
37
Returns: 0.6031
39
41
2
38
Returns: 0.1444
80
82
3
98
Returns: 0.9988159999999999
20
23
3
50
Returns: 0.125
900
902
4
43
Returns: 0.57590803
438
441
4
55
Returns: 0.39098125000000006
93
96
5
80
Returns: 0.9420800000000001
147
150
5
20
Returns: 0.05792000000000003
20
25
6
54
Returns: 0.15152445792000002
42
45
6
84
Returns: 0.9925184102399999
172
175
7
74
Returns: 0.9846563910336001
14
19
7
52
Returns: 0.2606678843392
691
696
8
16
Returns: 0.0038303055216639993
162
168
8
14
Returns: 1.633276830976001E-4
367
373
9
45
Returns: 0.16582204764843755
573
576
9
27
Returns: 0.4552306842262887
770
777
10
28
Returns: 0.007003913649746088
961
967
10
65
Returns: 0.7514955091185547
339
345
11
34
Returns: 0.13235007447814498
757
764
11
25
Returns: 0.007561206817626953
927
932
12
43
Returns: 0.6443261166261832
201
207
12
51
Returns: 0.6395748104688188
9
13
13
27
Returns: 0.13935305894741862
27
31
13
33
Returns: 0.4036756715317635
953
965
14
91
Returns: 0.8744890267682135
105
113
14
88
Returns: 0.9994230335926174
694
707
15
75
Returns: 0.2360878111794591
5
16
15
55
Returns: 0.10345875012448452
20
34
16
99
Returns: 0.9994920575907095
35
41
17
26
Returns: 0.18130082314428705
24
30
18
31
Returns: 0.21150614403517082
155
162
19
38
Returns: 0.5952235876407102
37
44
20
30
Returns: 0.2439854616048496
86
104
21
90
Returns: 0.8480346894280453
13
30
22
59
Returns: 0.05916231444619313
43
58
23
49
Returns: 0.08700240819422014
24
38
24
60
Returns: 0.5940784635646947
100
122
25
43
Returns: 4.063783527013334E-6
2
19
26
77
Returns: 0.5504215617924308
57
64
27
43
Returns: 0.6654143721112978
869
882
28
33
Returns: 0.09651040771505859
725
750
29
70
Returns: 0.037894911252999625
60
84
30
52
Returns: 0.0014688093488389015
20
50
31
94
Returns: 0.43751569726666195
11
37
32
90
Returns: 0.9607183600737896
47
70
33
66
Returns: 0.3992715855813985
22
52
34
96
Returns: 0.9891754176464141
33
62
35
53
Returns: 2.2468605836139833E-4
354
386
36
78
Returns: 0.07751563458344804
126
158
37
90
Returns: 0.8402196838785219
621
640
38
55
Returns: 0.781033644895088
154
172
39
41
Returns: 0.28294709560534465
320
349
40
56
Returns: 0.024190398892661856
89
94
41
14
Returns: 0.07484514677560127
2
13
42
62
Returns: 0.2368201057373569
159
193
43
74
Returns: 0.28622415983107474
19
39
44
73
Returns: 0.9273420872873085
1
46
45
99
Returns: 0.6361854860638709
793
833
46
85
Returns: 0.45357084090652705
464
485
47
43
Returns: 0.4366692587615992
45
80
48
71
Returns: 0.4520093300008817
205
249
49
84
Returns: 0.18263230249950224
33
45
50
41
Returns: 0.41060608474568533
13
15
6
0
Returns: 0.0
13
15
6
100
Returns: 1.0
972
1000
39
67
Returns: 0.3262616555347305
990
1000
50
50
Returns: 0.980639377210653
100
1000
50
50
Returns: 0.0
10
40
50
25
Returns: 7.476787558840655E-8
10
20
20
50
Returns: 0.3441343307495117
975
1000
50
49
Returns: 0.49472519628223177
150
190
50
20
Returns: 1.2907778453341292E-19
10
1000
50
10
Returns: 0.0
1
1000
50
67
Returns: 0.0
1
1000
50
50
Returns: 0.0
500
1000
50
50
Returns: 0.0
970
1000
50
60
Returns: 0.5605893505699144
500
1000
50
60
Returns: 0.0
965
987
50
32
Returns: 0.04802096739937314
999
1000
50
100
Returns: 1.0
998
1000
1
100
Returns: 0.0
510
540
50
50
Returns: 0.10118145797005695
10
1000
50
2
Returns: 0.0