Problem Statement
Misko and Danka are playing with a D-sided die. The die has faces numbered from 1 to D and it is a fair die: whenever rolled, each number will come up with probability 1 / D.
In their current game Misko is repeatedly rolling the die and Danka is taking notes as follows: After the very first roll, she does nothing. After each of the following rolls, she writes down the (non-negative) difference between the current and the previous outcome.
You are given the
Misko knows that Danka will not be happy until she has seen each possible difference occur at least once. He now wonders how many additional rolls this will take. Calculate and return the expected number of extra rolls needed until Danka will be happy.
Definition
- Class:
- SeeAllDifferences
- Method:
- solve
- Parameters:
- int, int[]
- Returns:
- double
- Method signature:
- double solve(int D, int[] rolled)
- (be sure your method is public)
Notes
- Your answer will be accepted if it has an absolute or a relative error at most 10^(-9).
Constraints
- D will be between 2 and 16, inclusive.
- rolled will contain between 1 and 50 elements, inclusive.
- Each element of rolled will be between 1 and D, inclusive.
Examples
2
{1,2,1}
Returns: 2.0
The kids have a 2-sided die, i.e., a coin with sides labelled 1 and 2. Misko already tossed the coin three times. Danka has already written down the difference 1 twice. In order for Danka to be happy, she also needs to see the difference 0. In each of the following coin tosses this will happen with probability 1/2. From this, we can show that the expected number of coin tosses until it happens is 1 / (1/2) = 2.
6
{3, 3, 4, 6, 1, 5, 2, 3, 4, 2, 2, 6}
Returns: 0.0
Danka has already been happy for a while: here, the first six differences have already all been distinct.
4
{2}
Returns: 11.896969696969695
6
{1}
Returns: 23.771221030410732
6
{2}
Returns: 25.271382862323605
6
{4}
Returns: 25.502719964893075
16
{4}
Returns: 168.0875346643678
2
{1}
Returns: 3.0
2
{2}
Returns: 3.0
3
{1}
Returns: 6.785714285714286
3
{1, 2, 3, 2}
Returns: 6.857142857142858
3
{1, 3, 1, 3, 2, 1, 2, 3, 1, 2, 3, 2, 3, 2, 1, 3, 2, 2, 3, 3, 1, 2, 2, 3, 2}
Returns: 0.0
3
{2}
Returns: 6.857142857142857
3
{2, 1, 1, 3, 3, 1}
Returns: 0.0
3
{2, 2, 1, 3, 2, 3, 3, 3, 3, 2, 3, 3, 2, 1, 3, 1, 1, 2, 2, 3, 1, 1, 2, 1, 1, 1, 1, 3, 3, 2, 3, 2}
Returns: 0.0
3
{3, 1, 3, 1, 2, 2}
Returns: 0.0
3
{3, 3}
Returns: 6.0
4
{1, 1, 4, 4, 1, 4, 1, 3, 4, 1, 2, 3, 3, 2, 4, 1, 1, 4, 4, 3, 1}
Returns: 0.0
4
{3}
Returns: 11.896969696969697
4
{3, 1, 3, 4, 4, 1, 1, 4, 3, 3, 4, 2, 1, 1, 3, 4, 3, 3, 1, 1, 4, 3, 1}
Returns: 0.0
4
{3, 4, 4, 3}
Returns: 10.8
4
{4}
Returns: 10.936363636363636
4
{4, 1}
Returns: 6.715151515151514
4
{4, 1, 3, 1, 3, 1, 2, 2, 4, 2, 4, 4, 1, 1, 2, 2, 3, 1, 2, 1, 4, 1, 1, 1, 3, 1, 3, 2, 2, 3, 1, 4, 3, 1, 1, 4, 4, 3, 3, 4}
Returns: 0.0
4
{4, 3, 3, 2, 3}
Returns: 10.8
5
{2, 5, 4, 1, 1, 4, 4, 5, 4, 5, 3, 3, 1, 3, 1, 2, 4, 3, 4, 4, 2, 5, 5, 5, 3, 3, 5, 1, 5, 4, 5, 5, 5, 5, 4, 5}
Returns: 0.0
5
{4}
Returns: 18.017089951445744
5
{4, 1, 2, 5, 2, 5, 1, 4, 4, 1, 2, 4, 2, 5, 4, 1, 5, 2, 1, 5, 4, 1}
Returns: 0.0
5
{4, 3, 1, 5, 4, 1, 1, 4, 4, 5, 1, 5, 2, 4, 4, 4}
Returns: 0.0
5
{4, 5, 5, 3, 4, 2, 3, 4, 1, 2, 4, 3, 1, 3, 4, 1, 3, 1, 4}
Returns: 14.99999999999999
5
{5}
Returns: 16.79429713353923
5
{5, 2}
Returns: 16.95285167830336
5
{5, 2, 5, 2, 5, 3, 3, 5, 5, 1, 5, 1, 3, 2, 4, 2, 4, 5, 4}
Returns: 0.0
6
{1}
Returns: 23.771221030410732
6
{1, 6, 5, 3, 1}
Returns: 13.227365728900258
6
{2, 3, 1, 5, 4, 1, 4, 5, 1}
Returns: 19.8
6
{2, 6}
Returns: 21.898764696426415
6
{4}
Returns: 25.502719964893075
6
{4, 6}
Returns: 23.405447011452214
6
{5}
Returns: 25.271382862323605
6
{6, 5, 4, 6, 5, 1, 2, 2, 6, 1, 5, 4, 3, 2, 6, 2}
Returns: 6.0
7
{1}
Returns: 32.05977172938717
7
{1, 6, 6, 5, 4, 3, 7, 7}
Returns: 27.004855605778943
7
{2, 2}
Returns: 33.32380468483808
7
{3, 3, 2, 5, 2, 3, 3, 2, 2, 4, 5, 1, 7, 6, 7, 3, 5, 6, 3, 4, 1, 4, 7, 4, 3, 7, 4, 3, 1, 6, 5, 6, 6}
Returns: 0.0
7
{3, 4, 1, 7, 1, 4, 2, 7, 4, 3, 5, 1}
Returns: 7.000000000000002
7
{4, 7, 7, 1, 1, 4, 3}
Returns: 17.444764451206655
7
{6}
Returns: 33.80823576195143
7
{7, 2, 3, 1, 1, 5, 5, 7, 1, 3, 5, 2, 5, 3, 4, 2}
Returns: 0.0
8
{1}
Returns: 41.548686848497226
8
{1, 2, 1, 5, 1, 4, 1, 1, 1, 7, 8, 4, 2, 5, 7, 6, 1, 2, 5, 5, 1, 8, 8, 7, 6, 2, 5, 7}
Returns: 0.0
8
{3, 3, 7, 8, 5, 3, 2, 1, 4, 3, 2, 1, 3, 2, 3}
Returns: 42.43116455209102
8
{3, 4}
Returns: 43.99512997992261
8
{5}
Returns: 44.05806895739805
8
{7, 7}
Returns: 43.14772848718872
8
{7, 7, 3, 5, 1}
Returns: 40.30727868726132
8
{7, 8, 1, 3, 3, 4, 2, 3, 5, 8, 8, 8, 5, 7, 8, 3, 1, 7, 8, 8, 7, 6, 6, 5, 5, 7}
Returns: 8.000000000000002
8
{8}
Returns: 41.548686848497226
9
{1}
Returns: 52.330326980093645
9
{5, 7, 2, 5, 9, 6, 2, 7, 6, 9, 4, 5, 5, 6, 1, 4, 5, 8, 6, 2, 3, 3, 5, 6, 5, 2, 5, 4, 1, 5, 4, 4, 8, 8, 2, 7, 1, 3, 2, 7, 5, 4, 7, 4, 2, 4}
Returns: 51.479999999999876
9
{6}
Returns: 55.18967230026436
9
{9}
Returns: 52.33032698009364
9
{9, 2, 9, 7, 5, 6, 6, 2, 2, 6, 8, 4, 2, 2, 9, 6, 8, 4, 1, 6, 5, 7, 5, 1, 2, 5, 8, 9, 4, 9, 9, 8, 5, 6, 7, 9, 4, 6, 4, 3, 4, 4, 1, 1, 9, 5, 5}
Returns: 14.999999999999993
9
{9, 5, 3, 8, 7, 2, 2, 1, 6}
Returns: 53.71326629520692
9
{9, 6, 9, 3}
Returns: 53.6178075117419
10
{1, 9}
Returns: 62.08013898500211
10
{4}
Returns: 67.54881821088053
10
{4, 5, 4, 1, 3, 4, 8, 2, 6, 9, 4, 6, 2, 5, 9, 3, 5, 6, 3, 3}
Returns: 65.21348505598796
10
{5, 1, 6}
Returns: 67.11815496079878
10
{7}
Returns: 67.54881821088055
10
{8, 5, 2}
Returns: 66.76807822705828
10
{9, 1, 9, 8, 9, 8, 10, 3, 3, 4, 5, 6, 4, 9, 8, 9, 5, 8, 5, 6}
Returns: 57.352661596958235
10
{10}
Returns: 64.33899726708106
10
{10, 8, 10, 3, 3, 4}
Returns: 65.2500990015067
11
{2, 5, 5, 3, 7, 11, 4, 4}
Returns: 79.71872507792703
11
{4}
Returns: 81.17237286367094
11
{5, 10, 1, 5, 1, 11, 2, 10, 10, 7, 10, 9, 7}
Returns: 21.323203079592634
11
{6, 2, 11, 8, 5, 5, 10, 6, 4, 1, 5, 8, 4, 11, 2, 9, 5, 3, 7, 5, 10, 4, 9, 5, 3, 3, 6, 3}
Returns: 70.56842041257511
11
{7, 11, 9, 4}
Returns: 80.75494762388824
11
{8, 9, 3, 5, 7, 6, 6, 2, 7, 7, 3, 2, 7, 4, 4, 1, 5, 9, 1, 6, 7, 9, 5, 4, 5, 2, 11, 1, 4, 3}
Returns: 15.124999999999993
11
{9}
Returns: 80.99339558950605
11
{10, 5, 5, 11, 8, 1, 5, 4, 1, 7, 3, 5, 8, 4, 8, 1, 6, 11, 4, 7, 9, 3, 3, 3, 10, 1, 4, 6, 10, 7, 11, 5, 5, 11, 2, 5, 4, 1, 9, 8, 5, 4, 5, 8, 3, 3, 9, 5}
Returns: 65.99999999999983
12
{1, 2, 11, 9, 4, 4, 2, 4, 8, 7, 5, 12, 5}
Returns: 92.15765680306318
12
{3, 8, 10, 10}
Returns: 95.38122239447739
12
{4}
Returns: 96.0404923191923
12
{5, 9, 3}
Returns: 95.483558425623
12
{6}
Returns: 96.1460102884851
12
{6, 5}
Returns: 96.09699111248632
12
{6, 7}
Returns: 96.12506378285629
12
{8}
Returns: 96.11808007273869
12
{10, 12, 12, 3, 4, 11, 8, 9, 12, 11, 4, 1, 12, 3, 1, 10, 6, 4, 11, 6, 4, 4, 8, 6}
Returns: 46.43110439066612
13
{1}
Returns: 107.94986715326701
13
{6}
Returns: 112.29540144659258
13
{8, 4, 7, 4, 12, 1, 4, 8, 9, 1, 9, 5, 8, 6, 5, 10, 12, 11, 9}
Returns: 101.971591915629
13
{8, 13, 8}
Returns: 112.19968647864678
13
{9}
Returns: 112.25955445151637
13
{9, 2, 10, 12, 9, 3, 4, 6, 8, 9, 12, 12, 5, 2, 6, 13, 5, 1, 11, 9, 5, 9, 5, 8, 9, 10, 8, 3, 6, 3, 11, 4, 1, 2, 1, 7, 8, 4, 11, 11, 9, 11, 10, 3, 11, 12, 6, 1, 9, 12}
Returns: 105.80061726996729
13
{13, 1, 7, 10}
Returns: 64.92135510270916
13
{13, 7, 8}
Returns: 112.11061121746596
14
{3, 3, 7, 7, 10, 13, 6, 11, 3, 10, 14, 13, 7, 1, 2, 7, 12, 3, 11, 14, 2, 2, 3, 2, 13, 2, 13, 14}
Returns: 104.16242561144985
14
{6}
Returns: 129.692232869709
14
{6, 8, 1, 5, 10, 8, 8, 3, 2, 5, 6, 8, 1, 8, 12, 1, 7, 11, 2, 12, 13, 12, 4, 6, 4, 4, 12, 10, 3, 4, 8, 9, 12, 2, 5, 13, 10, 11, 12, 11}
Returns: 120.92499999999757
14
{9, 4, 7, 12, 8, 3, 11, 3, 3, 4, 13, 6, 1, 10, 9, 12, 4, 9, 14, 8, 3, 5, 9, 11, 7, 11, 8}
Returns: 127.649628353084
14
{12}
Returns: 129.31164559794252
14
{12, 8, 12, 12, 14, 12, 13, 14, 4}
Returns: 127.89127236042259
14
{13, 14, 8, 4, 1, 3, 12, 9, 13, 5, 3, 5, 6, 3, 14, 6, 14, 13, 11, 14}
Returns: 119.38637300334472
14
{14, 11, 1, 3, 10, 7, 7, 1, 9, 1, 1, 10, 12, 2, 4, 8, 4, 13, 9, 1, 13, 9, 13, 2, 1, 6, 5, 8, 5, 2}
Returns: 104.99999999999764
15
{1, 7, 3}
Returns: 147.80224863127293
15
{2, 3, 6, 11, 12, 3, 12, 3, 5}
Returns: 147.7905257764886
15
{2, 15, 4, 11, 12, 9, 7, 9, 11}
Returns: 133.5961298311996
15
{3, 14, 7}
Returns: 146.57689493926722
15
{6}
Returns: 148.34821030621134
15
{9}
Returns: 148.36981246031098
15
{10}
Returns: 148.34821030621134
15
{13, 15, 6, 4, 6, 5, 15, 4, 1, 5, 15, 1, 3, 15, 1, 9, 5, 5, 7}
Returns: 64.85814861724178
15
{14, 9}
Returns: 148.31744019033883
16
{2}
Returns: 166.98164557358288
16
{2, 6, 5, 7, 12, 12, 5, 2, 2, 5, 6, 6, 2, 1, 12, 7}
Returns: 166.9581336285952
16
{5, 6, 6, 15, 3, 7, 12, 13, 7, 16, 3, 16, 7, 2, 1, 11, 7, 13, 1, 5, 13, 12, 8, 4, 8, 7, 13, 9, 15, 13}
Returns: 159.1929982543925
16
{7}
Returns: 168.28112333165174
16
{8}
Returns: 168.29128913784461
16
{12, 6, 3, 9, 3, 16, 15}
Returns: 162.49284945066623
16
{13, 3, 3, 3}
Returns: 167.19445083673838
16
{13, 6, 10, 4, 15, 14, 9, 8, 8, 2, 6, 2, 10, 14, 16, 8, 7, 2, 9, 7, 2, 11, 9, 5, 14, 4, 4, 8, 6, 6, 4, 13, 11, 9, 1, 9, 6, 1, 10, 10}
Returns: 165.6630855247203
16
{7 }
Returns: 168.28112333165174
16
{8, 9 }
Returns: 168.28323310845178
16
{8 }
Returns: 168.29128913784461
16
{1 }
Returns: 162.86537839122823