Problem Statement
Yvonne and Zara are playing a game again. In this game their simultaneously choose a positive integer. (The chosen numbers can be arbitrarily large.) The goal of the game is to choose a number that is slightly larger than your opponent's number. More precisely:
- If the numbers are equal, the game is a draw and there is no payment.
- If the bigger number minus the smaller number is at most maxDiff, the person with the bigger number wins and gets ifNear dollars from the loser.
- If the difference is larger, the person with the bigger number loses and pays ifFar dollars to the winner. The ifFar payoff is at least as big as the ifNear payoff.
You are given the values mentioned above and an
Definition
- Class:
- SlightlyBigger
- Method:
- getProbability
- Parameters:
- int, int, int, int
- Returns:
- double
- Method signature:
- double getProbability(int maxDiff, int ifNear, int ifFar, int query)
- (be sure your method is public)
Notes
- Your return value will be accepted if it has an absolute or a relative error at most 1e-9.
- The constraint "ifFar <= 2*ifNear" has no significance in terms of the solution idea, it was just added to (hopefully) avoid precision issues with numbers getting too close to zero.
Constraints
- maxDiff will be between 1 and 25, inclusive.
- ifNear will be between 1 and 50, inclusive.
- ifFar will be between ifNear and 2*ifNear, inclusive.
- query will be between 1 and 1000, inclusive.
Examples
1
1
1
1
Returns: 0.3333333333333334
If your number is exactly one bigger than your opponent's, you win $1. If your number is bigger than that, you lose $1. In this setting, Yvonne should choose the integer 1 with probability 1/3.
1
1
1
470
Returns: 0.0
In the same setting as before, the probability with which Yvonne should choose the integer 470 is either zero or negligibly small.
1
1
2
1
Returns: 0.25
In the new setting you pay $2 if you exceed your opponent's number by more than 1 (and, symmetrically, you get paid $2 when your opponent's number exceeds yours by two or more). Perhaps surprisingly, in the new setting the optimal probability for the choice of the smallest possible integer is lower than before.
3
4
7
3
Returns: 0.08005718370264478
1
1
2
2
Returns: 0.5
1
1
2
3
Returns: 0.25
1
1
2
4
Returns: 0.0
1
1
1
2
Returns: 0.3333333333333333
1
1
1
3
Returns: 0.3333333333333333
1
1
1
4
Returns: 0.0
9
29
29
4
Returns: 0.05263157894736842
23
32
64
8
Returns: 2.403730777755797E-7
17
21
34
13
Returns: 1.694690645831155E-4
15
39
44
13
Returns: 0.020819861304758547
23
25
26
12
Returns: 0.0018334504552429687
18
2
4
25
Returns: 4.31333542065139E-6
22
19
20
17
Returns: 0.007367190505527801
16
47
81
1
Returns: 0.17119709574783865
12
44
62
25
Returns: 0.16236383610545185
18
24
27
6
Returns: 0.0036527924929422866
8
39
46
7
Returns: 0.039443269327903895
25
26
34
47
Returns: 0.0019305590592245726
2
15
29
2
Returns: 0.09489666807254324
1
11
19
3
Returns: 0.26829268292682923
12
38
41
13
Returns: 0.13937524696207446
4
27
40
6
Returns: 0.08699912981234999
9
19
22
10
Returns: 0.19508639874999018
3
12
14
5
Returns: 0.12238950947061678
17
49
53
19
Returns: 0.08003266192107528
19
23
39
26
Returns: 2.268171562569751E-5
20
38
76
40
Returns: 0.024922359499621523
13
40
42
26
Returns: 0.05755275028749916
6
28
38
8
Returns: 0.0886202151846674
18
38
55
37
Returns: 0.16442188583372075
14
45
56
6
Returns: 0.0011364676390520996
15
37
73
1
Returns: 0.17102493960988824
9
17
23
10
Returns: 0.2847557680120154
20
35
65
28
Returns: 1.5067958161898578E-6
15
18
35
22
Returns: 5.7166399690006345E-6
24
5
9
443
Returns: 0.0
3
24
24
3
Returns: 0.14285714285714285
18
20
27
35
Returns: 0.015351905207100504
3
33
40
4
Returns: 0.24355914289498654
16
25
27
7
Returns: 0.004084777213584882
20
26
26
40
Returns: 0.024390243902439032
17
46
83
31
Returns: 1.6382829712710694E-4
25
44
57
47
Returns: 0.002086830590448196
4
33
58
2
Returns: 0.034150480049173766
11
36
72
7
Returns: 3.1211473337597636E-5
9
7
10
11
Returns: 0.08589708511575558
20
12
22
32
Returns: 2.264367741242107E-8
25
3
5
42
Returns: 1.0337873891198492E-7
1
38
44
3
Returns: 0.31666666666666665
12
38
62
17
Returns: 7.491240127145851E-4
8
36
52
12
Returns: 0.006450857441950323
25
6
6
18
Returns: 0.0196078431372549
8
33
65
9
Returns: 0.4417261917133089
14
27
44
4
Returns: 0.001635650761035802
8
23
33
6
Returns: 0.006666478866203876
5
38
68
444
Returns: 0.0
11
37
64
8
Returns: 5.141253505561793E-4
21
3
4
4
Returns: 0.005144632648322613
19
3
6
20
Returns: 0.44721359549995804
2
36
59
3
Returns: 0.38649206206834685
5
12
23
9
Returns: 0.005937423547308512
16
13
25
32
Returns: 0.02682072452798106
22
2
2
1
Returns: 0.02222222222222223
15
2
3
26
Returns: 1.6307830818139985E-4
16
48
55
27
Returns: 0.001443514148181717
12
5
8
18
Returns: 1.9157098026936163E-4
15
43
62
15
Returns: 0.08543197455799505
3
7
11
4
Returns: 0.3575838478224596
20
48
75
24
Returns: 0.004307865754468971
16
48
77
24
Returns: 8.999899682721426E-6
24
24
42
20
Returns: 8.844704334467288E-5
7
9
10
3
Returns: 0.03750188169531313
19
22
30
33
Returns: 1.2753228932096863E-4
1
37
52
1
Returns: 0.29365079365079355
4
2
2
5
Returns: 0.11111111111111109
15
34
62
20
Returns: 3.6515344319606145E-4
10
37
68
20
Returns: 0.029162030967835893
15
40
75
6
Returns: 2.028379777878619E-5
24
3
4
22
Returns: 0.009093610287999805
17
33
55
29
Returns: 1.2226216869763316E-5
23
2
4
13
Returns: 3.0103081138932453E-10
25
29
39
44
Returns: 4.757220639307904E-5
19
32
53
36
Returns: 0.0014948277119996758
6
40
44
8
Returns: 0.08957077820940747
16
17
34
10
Returns: 6.344214761028309E-7
17
44
74
21
Returns: 0.0030679621160790045
25
50
75
3
Returns: 0.010416666666671464