Problem Statement
You have a collection of N dice. Each die has D faces. The faces of each die are numbered from 1 to D. All dice are fair: whenever rolled, each of the numbers will come up with probability 1 / D.
In the beginning, all dice are placed on the table so that each of them shows the number D. Your goal is to create a state in which all your dice show the number 1 instead.
You are going to reach the goal via a sequence of actions. In each action you can select an arbitrary subset of dice (regardless of what number they currently show), pick them up and reroll them. Each such action counts as one additional roll, regardless of how many dice you rerolled.
You are trying to minimize the expected number of rolls needed to reach the given goal. Assuming you are using the best possible strategy, what is this expected number of rolls? Calculate and return it.
Definition
- Class:
- RollAllOnes
- Method:
- solve
- Parameters:
- int, int
- Returns:
- double
- Method signature:
- double solve(int N, int D)
- (be sure your method is public)
Notes
- Your answer will be accepted if it has a relative error at most 10^(-9).
- Each time you roll some dice, the new value visible on each die is chosen uniformly at random. All these random choices are mutually independent.
Constraints
- N will be between 1 and 50, inclusive.
- D will be between 2 and 20, inclusive.
Examples
1
6
Returns: 6.000000000000002
You have a single six-sided die. The best you can do is reroll it until you get a 1. As in each roll this has a probability p = 1/6 of happening, the expected number of attempts until it happens is 1/p = 6.
2
2
Returns: 2.6666666666666665
Two coins, each with the number 1 on one side and the number 2 on the other side.
3
10
Returns: 17.900563216158464
Three 10-sided dice.
1
2
Returns: 2.0
1
20
Returns: 19.999999999999982
50
20
Returns: 88.21527335201547
47
19
Returns: 82.58233634841167
47
20
Returns: 87.02132593004009
48
19
Returns: 82.96765915294772
49
7
Returns: 29.55731809518341
45
12
Returns: 51.01003980864585
41
13
Returns: 54.25796756387642
38
17
Returns: 70.23902494760323
29
3
Returns: 10.27064047863805
44
4
Returns: 15.699855368331852
10
11
Returns: 31.23090681374826
3
9
Returns: 16.06532935754946