Problem Statement
"What's more likely? A single A, or a double B?"
This is the question Alice and Bob have been pondering since early morning today.
Let's explain what's going on. Alice and Bob are generating a sequence of random numbers. Each number is generated by rolling N standard D-sided dice and summing up the values rolled.
(A standard D-sided die has D faces with numbers 1 to D on them. Whenever the die is rolled, each face will come up with probability 1 / D.)
Alice wins as soon as the value A appears in the sequence. Bob wins if the value B appears in the sequence twice in a row. As soon as either player wins, the game is over.
For example, suppose A=2 and B=7. If the sequence of numbers starts 4, 7, 11, 7, 5, 2, ... after the sixth number Alice wins the game.
(Note that Bob did not win after the fourth number: the number 7 did appear twice, but the appearances were not consecutive.)
Given the
Definition
- Class:
- SingleOrDouble
- Method:
- probAlice
- Parameters:
- int, int, int, int
- Returns:
- double
- Method signature:
- double probAlice(int N, int D, int A, int B)
- (be sure your method is public)
Notes
- The return value must have an absolute error at most 10^(-6) to be accepted.
- All rolls of dice are mutually independent.
Constraints
- N will be between 1 and 10, inclusive.
- D will be between 2 and 10, inclusive.
- A will be between N*1 and N*D, inclusive.
- B will be between N*1 and N*D, inclusive.
- A will not be equal to B.
Examples
1
2
1
2
Returns: 0.75
Each number is generated by rolling a single two-sided die - in other words, by flipping a coin with "1" on one side and "2" on the other side. Alice is waiting for a single 1. Bob is waiting for a double 2. If either of the first two throws is a 1, Alice wins. If both are 2, Bob wins. In either case the game will be over after at most two throws.
1
6
1
2
Returns: 0.8749999999999999
Same game as in Example 0, but now with a standard 6-sided die. Alice is still a strong favorite in this game. Intuitively, Bob getting a single 2 has the same probability as Alice getting a single 1, and thus Bob getting a double 2 before Alice getting a single 1 must be very unlikely. However, with a six-sided die the players can sometimes generate numbers other than 1 and 2, and it can sometimes take very many turns until one of the players wins. This influences our answer - you may note that the return value in this test case differs from the return value in Example 0.
2
6
2
7
Returns: 0.5384615384615384
Two standard dice are used to generate the numbers. Alice is waiting for a single appearance of the least likely number (2), Bob is waiting for two consecutive appearances of the most likely number (7). It turns out that this game is almost fair, Alice only has a tiny edge over Bob.
3
10
29
16
Returns: 0.36440677966101687
Here the value Alice wants is so unlikely that Bob is actually the favorite to win the game, even though he's waiting for a double.
10
2
15
10
Returns: 0.9999961285477021
10
2
10
15
Returns: 0.01969743748070392
10
10
55
10
Returns: 1.0
10
10
10
55
Returns: 5.578269057480362E-8
6
10
42
8
Returns: 0.9999999829910622
4
2
8
6
Returns: 0.3793103448275862
6
3
12
14
Returns: 0.9344548831112083
3
4
10
6
Returns: 0.8161764705882353
6
8
20
21
Returns: 0.9543489336924085
5
5
22
13
Returns: 0.540755690099787
4
5
5
8
Returns: 0.6830530401034929
5
10
19
43
Returns: 0.9995996370630934
9
10
54
65
Returns: 0.9977645961636101
6
3
11
15
Returns: 0.9751624376577186
6
2
10
8
Returns: 0.8404255319148937
3
3
4
8
Returns: 0.9090909090909091
2
4
8
3
Returns: 0.8181818181818182
7
2
8
7
Returns: 0.9988938053097345
2
8
8
7
Returns: 0.9315589353612167
2
2
2
3
Returns: 0.6
8
2
14
16
Returns: 0.999861053216618
2
6
9
10
Returns: 0.9454545454545455
8
7
24
40
Returns: 0.9745402233848653
4
7
10
19
Returns: 0.8699860355371504
5
9
43
13
Returns: 0.7847230459020282
7
10
39
19
Returns: 0.999934276790755
10
6
49
46
Returns: 0.9644959956087542
6
7
41
42
Returns: 0.999998583370756
4
9
33
4
Returns: 0.9999923804298961
1
10
5
4
Returns: 0.9166666666666666
6
2
10
7
Returns: 0.9668508287292817
10
7
43
35
Returns: 0.9647325803272271
2
8
3
7
Returns: 0.7954545454545454
5
10
14
33
Returns: 0.7987806738817935
9
10
69
64
Returns: 0.9642186857584869
1
6
1
2
Returns: 0.8749999999999999
8
6
44
33
Returns: 0.07891068934376197
3
10
29
18
Returns: 0.3765793167992512
9
7
49
11
Returns: 0.9999999998083885
1
4
1
3
Returns: 0.8333333333333334
10
10
96
70
Returns: 5.379554326264801E-4
10
5
13
34
Returns: 0.006557897446747737
7
8
46
9
Returns: 0.999999952146016
5
9
39
5
Returns: 0.9999999193580968
8
2
9
15
Returns: 0.9705882352941176
2
5
8
9
Returns: 0.9529411764705883
4
7
17
26
Returns: 0.9998148710391659
2
9
12
3
Returns: 0.9931623931623932
2
10
5
16
Returns: 0.9438202247191011
2
6
9
2
Returns: 0.9932885906040269
8
6
48
42
Returns: 0.36561744605083124
10
10
29
80
Returns: 0.9987155597684634
2
8
11
7
Returns: 0.9210526315789473
2
5
7
4
Returns: 0.9256198347107438
10
10
10
100
Returns: 0.9999999999
10
10
99
100
Returns: 0.99999999999
10
10
50
49
Returns: 0.9690668456934114
10
10
100
90
Returns: 0.539613903360344
10
10
11
10
Returns: 0.99999999999
10
10
10
13
Returns: 0.9999951600235321
10
10
10
11
Returns: 0.9999999900000002
8
10
12
20
Returns: 0.9293483185234206
10
5
12
11
Returns: 0.9999998138184072
10
10
100
18
Returns: 0.9442001626737733
10
10
11
47
Returns: 1.1480947995650973E-6