Problem Statement
Fox Ciel is sailing in the Donut sea. The Donut sea is a torus. For navigation, the torus is divided into N times M cells, as shown in the figure below.
(Image by YassineMrabet from Wikimedia Commons, licensed under CC BY-SA 3.0.)
Each of the cells has two integer coordinates (n, m), where 0 <= n < N and 0 <= m < M. Note that the coordinates wrap around modulo N and M. For example, if you are in the cell (N-1, M-1) and you cross over one of its sides, you will reach one of the cells (N-2, M-1), (0, M-1), (N-1, M-2), and (N-1, 0).
Ciel starts in the cell (0, 0) and wants to reach the goal cell (goalX, goalY).
Unfortunately, Ciel's navigation is very poor. Whenever she moves to a new cell, there are two equally probable outcomes: either her first or her second coordinate increases by one (wrapping around if necessary). Formally, if Ciel's current coordinates are (n, m), her new coordinates will be either ((n+1) modulo N, m), or (n, (m+1) modulo M), with equal probability. Each such move takes one day.
Return the expected number of days Ciel will need to reach her goal.
Definition
- Class:
- TorusSailing
- Method:
- expectedTime
- Parameters:
- int, int, int, int
- Returns:
- double
- Method signature:
- double expectedTime(int N, int M, int goalX, int goalY)
- (be sure your method is public)
Notes
- The returned value must have an absolute or relative error less than 1e-9.
Constraints
- N will be between 2 and 100, inclusive.
- M will be between 2 and 100, inclusive.
- goalX will be between 0 and N - 1, inclusive.
- goalY will be between 0 and M - 1, inclusive.
- (goalX, goalY) will not be (0, 0).
Examples
2
2
1
1
Returns: 4.0
She can reach the goal in 2 days with probability 1/2, in 4 days with probability 1/4, in 6 days with probability 1/8, in 8 days with probability 1/16, and so on. In general, she can reach the goal in 2*n days with probability 1/(2^n) where n is a positive integer. The answer is (2 * 1/2) + (4 * 1/4) + (6 * 1/8) + (8 * 1/16) + ... = 4.0
3
3
0
2
Returns: 8.0
7
10
3
2
Returns: 51.80060107964039
100
100
99
99
Returns: 9992.616372325532
2
4
0
1
Returns: 3.8000000000000003
2
4
1
3
Returns: 8.8
2
9
1
4
Returns: 14.074382684686519
2
29
0
19
Returns: 57.333333316699395
2
33
0
32
Returns: 86.00000000000006
2
35
1
6
Returns: 35.36534064929129
2
41
0
29
Returns: 85.33333333333299
2
57
0
4
Returns: 45.530864197530875
2
71
1
53
Returns: 153.33333333333337
2
84
1
29
Returns: 114.00000000000094
2
97
1
29
Returns: 122.66666666666788
3
6
2
5
Returns: 18.59340659340659
3
8
0
3
Returns: 17.270493103313793
3
8
2
1
Returns: 17.667232615280614
4
4
1
3
Returns: 14.399999999999999
4
74
0
27
Returns: 221.73333328896143
5
7
4
4
Returns: 30.970665141436612
5
34
3
21
Returns: 149.48384912679867
5
45
3
29
Returns: 200.25806427882674
6
2
3
0
Returns: 9.857142857142858
6
7
2
3
Returns: 31.806096080018506
6
20
0
11
Returns: 103.79539187693247
6
30
0
7
Returns: 137.63320776515744
6
95
1
94
Returns: 577.0476190476198
7
4
0
1
Returns: 14.92393779465458
7
6
3
5
Returns: 38.2603510306902
7
9
6
8
Returns: 61.21955243016511
7
57
1
30
Returns: 348.1418559907895
8
5
1
0
Returns: 19.289672534866863
8
55
5
22
Returns: 375.7176269820045
9
2
0
1
Returns: 12.000609694136777
9
3
7
0
Returns: 26.86838113125766
9
10
5
0
Returns: 88.09838464566226
9
24
5
6
Returns: 171.53828722622777
10
5
9
1
Returns: 49.673166830308666
10
6
1
1
Returns: 31.079410584776475
10
7
7
2
Returns: 65.43257244102476
10
36
6
26
Returns: 340.3970656326253
10
88
8
26
Returns: 756.7805161471811
12
3
3
2
Returns: 24.082405410274255
13
2
8
1
Returns: 24.66799304030177
14
95
0
5
Returns: 1268.9842966611013
17
2
0
1
Returns: 22.666666842186554
18
8
8
4
Returns: 124.08669881445297
18
29
4
3
Returns: 383.62761791614207
20
10
7
0
Returns: 181.39053148465823
20
35
3
1
Returns: 528.3291317157722
21
28
4
12
Returns: 588.3230584169237
22
47
16
36
Returns: 1011.4699942870288
24
69
5
61
Returns: 1638.3123211756197
25
48
13
17
Returns: 1099.6553336341115
25
68
5
16
Returns: 1686.1103832044855
25
84
22
14
Returns: 2012.0669130276785
26
2
21
0
Returns: 59.333333331683185
27
41
18
37
Returns: 1091.165348353744
28
31
10
2
Returns: 873.4200250277795
30
40
27
35
Returns: 1181.4015716454364
31
15
11
13
Returns: 417.065003765284
31
68
10
8
Returns: 1771.187306682859
32
2
21
1
Returns: 63.33333333537281
33
9
16
3
Returns: 263.1098847673352
34
13
3
4
Returns: 326.6785614347832
38
47
26
43
Returns: 1829.90059976723
39
40
0
39
Returns: 1555.1254389160606
40
24
34
11
Returns: 926.0099169546604
40
32
39
14
Returns: 1261.2629181371847
42
15
16
2
Returns: 570.731314470298
42
88
23
61
Returns: 3607.747317443862
43
64
2
56
Returns: 2689.773574538708
43
98
2
44
Returns: 3938.112464212912
44
38
24
29
Returns: 1565.123001986724
47
40
3
31
Returns: 1964.3644465614852
48
56
9
42
Returns: 2675.5821677588624
50
28
23
26
Returns: 1302.7328635658164
50
71
16
30
Returns: 3501.1290118680054
51
2
34
0
Returns: 101.99999999999994
52
95
39
94
Returns: 4850.378739592303
53
80
32
3
Returns: 4097.147066832872
54
65
0
55
Returns: 3341.794720386737
57
65
1
39
Returns: 3705.750908690869
57
75
48
19
Returns: 4187.696644389268
58
58
15
13
Returns: 2972.358965759264
61
67
41
5
Returns: 4368.537865366961
62
76
30
11
Returns: 4544.9918364919495
65
73
7
40
Returns: 4919.731231666166
67
8
52
5
Returns: 508.10196104540023
67
9
65
6
Returns: 600.1800392201667
74
93
50
33
Returns: 6611.012837861477
80
47
12
12
Returns: 3172.5421624935807
83
59
16
15
Returns: 4230.312721204351
85
86
47
52
Returns: 7139.47043987844
85
93
67
87
Returns: 8319.231231606933
87
91
35
25
Returns: 7592.6730006157595
89
48
61
20
Returns: 4194.485276890517
90
90
61
86
Returns: 9014.144203285074
90
99
62
78
Returns: 9176.5833925519
91
93
36
37
Returns: 7909.219438664175
91
95
52
36
Returns: 8625.391240790024
91
95
88
4
Returns: 8949.031616931412
91
97
58
93
Returns: 9660.753110363148
92
90
11
32
Returns: 8756.319742653312
92
100
38
23
Returns: 8875.213645129132
93
90
57
81
Returns: 8848.029837295904
93
96
4
17
Returns: 9518.134168622015
94
2
92
0
Returns: 246.66666666666657
94
97
53
82
Returns: 10285.327719309254
95
90
58
75
Returns: 8514.14862230009
95
91
85
47
Returns: 9708.4312977524
95
92
38
53
Returns: 8773.601227631909
95
99
6
44
Returns: 10575.856192392523
95
100
22
80
Returns: 10156.896771791113
96
92
68
6
Returns: 9399.318891424467
96
98
20
39
Returns: 10282.796732740906
99
30
68
13
Returns: 2906.7601866291816
99
94
79
89
Returns: 9082.98332016824
100
5
25
1
Returns: 366.12902073839996
100
99
50
68
Returns: 10385.345282048595
100
100
11
1
Returns: 10245.825582311874
100
100
13
71
Returns: 11610.623329822454
100
100
19
85
Returns: 11416.546256976902
100
100
41
58
Returns: 10553.124874841615
100
100
44
90
Returns: 11658.292807872549
100
100
45
70
Returns: 11048.655012720867
100
100
52
18
Returns: 11418.374580028743
100
100
53
85
Returns: 11351.572324746736
100
100
63
86
Returns: 10933.07612527848
100
100
73
73
Returns: 9775.827352290125
100
100
84
88
Returns: 9940.226549754017
100
100
0
1
Returns: 5006.327157905663
100
100
1
0
Returns: 5006.327157905709
2
100
1
0
Returns: 133.33333333333337
100
2
0
1
Returns: 133.33333333333337
10
100
5
5
Returns: 749.9646811086918
77
11
3
3
Returns: 584.3216984146654
2
2
0
1
Returns: 3.0
2
2
1
0
Returns: 3.0