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 both of her coordinates increase by 1, or both of them decrease by 1 (wrapping around if necessary). Formally, if Ciel's current coordinates are (n, m), her new coordinates will be either ((n+1) modulo N, (m+1) modulo M), or ((n-1) modulo N, (m-1) modulo M), with equal probability. Each such move takes one day.
If Ciel can never reach her goal, return -1. Otherwise, return the expected number of days Ciel will need to reach her goal.
Definition
- Class:
- TorusSailingEasy
- 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.
- In many programming languages the modulo operator returns negative values for negative inputs. If you are using such a language, it is safer to use the formulas ((n-1+N) modulo N) and ((m-1+M) modulo M) to compute Ciel's new coordinates when both of them are supposed to decrease.
- Informally, the expected value of a random variable can be seen as its average over very many trials.
Constraints
- N will be between 2 and 10, inclusive.
- M will be between 2 and 10, 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: 1.0
She will always reach the goal in 1 day.
2
2
0
1
Returns: -1.0
It is impossible to reach the goal. Ciel will only visit the cells (0, 0) and (1, 1) alternately.
3
3
1
1
Returns: 2.0
She can reach the goal in 1 day with probability 1/2, in 2 days with probability 1/4, in 3 days with probability 1/8, in 4 days with probability 1/16 and so on. In general, she can reach the goal in n days with probability 1/(2^n) where n is a positive integer. The answer is (1 * 1/2) + (2 * 1/4) + (3 * 1/8) + (4 * 1/16) + ... = 2.0.
4
6
1
3
Returns: 27.0
2
2
1
0
Returns: -1.0
4
7
2
3
Returns: 180.0
6
8
3
6
Returns: -1.0
8
6
1
0
Returns: -1.0
10
10
9
9
Returns: 9.0
10
10
1
1
Returns: 9.0
10
9
9
8
Returns: 89.0
10
9
3
6
Returns: 1881.0
2
9
1
5
Returns: 65.0
2
5
1
3
Returns: 21.0
10
8
7
4
Returns: -1.0
6
8
1
3
Returns: 95.0
5
2
1
1
Returns: 9.0
7
2
1
1
Returns: 13.0
2
3
1
2
Returns: 5.0
3
2
0
1
Returns: 9.0
3
3
1
2
Returns: -1.0
3
4
2
0
Returns: 32.0
4
6
2
2
Returns: 20.0
6
4
1
0
Returns: -1.0
10
10
7
3
Returns: -1.0
10
10
9
1
Returns: -1.0
5
10
4
2
Returns: -1.0
5
10
1
3
Returns: -1.0
8
2
2
0
Returns: 12.0
10
3
8
1
Returns: 56.0
10
4
2
2
Returns: 36.0
10
9
5
0
Returns: 2025.0
9
10
0
5
Returns: 2025.0
3
9
1
7
Returns: 14.0
8
2
1
0
Returns: -1.0
10
7
7
1
Returns: 741.0
4
7
3
6
Returns: 27.0
10
9
1
1
Returns: 89.0
5
8
2
5
Returns: 111.0
8
5
2
4
Returns: 204.0
8
9
2
1
Returns: 620.0
8
6
1
4
Returns: -1.0
6
8
3
0
Returns: -1.0
8
5
2
3
Returns: 396.0
4
4
2
2
Returns: 4.0
5
9
4
8
Returns: 44.0
9
10
5
3
Returns: 1541.0
5
4
3
0
Returns: 96.0
3
7
1
5
Returns: 38.0
10
3
9
0
Returns: 189.0
7
10
0
9
Returns: 1029.0
4
8
2
2
Returns: 12.0
5
7
1
2
Returns: 304.0
10
6
3
2
Returns: -1.0
4
5
3
2
Returns: 91.0
6
9
4
8
Returns: -1.0
8
9
2
8
Returns: 1196.0
8
2
5
0
Returns: -1.0
9
2
5
0
Returns: 56.0
2
8
1
6
Returns: -1.0
7
5
5
4
Returns: 304.0
5
6
1
5
Returns: 209.0
5
3
3
0
Returns: 36.0
4
7
1
0
Returns: 147.0
4
9
1
1
Returns: 35.0
9
9
7
2
Returns: -1.0
5
9
3
5
Returns: 506.0
5
4
4
0
Returns: 64.0
7
4
1
3
Returns: 195.0
4
7
2
0
Returns: 196.0
10
2
2
0
Returns: 16.0
4
10
2
3
Returns: -1.0
5
7
3
6
Returns: 286.0
9
9
7
1
Returns: -1.0
5
9
3
3
Returns: 126.0
5
4
3
1
Returns: 91.0
2
4
1
3
Returns: 3.0
7
5
2
2
Returns: 66.0
6
4
3
0
Returns: -1.0
5
4
1
1
Returns: 19.0
2
9
0
7
Returns: 32.0
9
4
4
3
Returns: 155.0
6
10
5
4
Returns: -1.0
2
10
0
9
Returns: -1.0
9
4
1
3
Returns: 323.0
6
10
1
4
Returns: -1.0
10
3
0
2
Returns: 200.0
3
10
2
0
Returns: 200.0
7
10
5
1
Returns: 549.0
4
2
0
1
Returns: -1.0
5
6
2
5
Returns: 221.0
7
4
2
1
Returns: 171.0
10
8
2
5
Returns: -1.0
10
2
9
1
Returns: 9.0
9
7
4
5
Returns: 920.0
7
7
1
5
Returns: -1.0
10
10
8
9
Returns: -1.0
10
9
3
4
Returns: 1001.0
9
10
1
5
Returns: 1925.0
9
7
4
0
Returns: 686.0
5
2
0
1
Returns: 25.0
3
3
2
1
Returns: -1.0
10
9
6
1
Returns: 2024.0
10
9
4
8
Returns: 2024.0
9
10
4
7
Returns: 1541.0
10
9
9
0
Returns: 729.0
5
7
2
1
Returns: 286.0
9
5
6
0
Returns: 450.0
5
8
3
1
Returns: 231.0
5
8
3
2
Returns: 396.0
9
3
6
0
Returns: 18.0
2
10
1
2
Returns: -1.0
3
10
1
9
Returns: 209.0
4
3
3
2
Returns: 11.0
3
8
2
2
Returns: 44.0
7
7
5
4
Returns: -1.0
5
5
2
2
Returns: 6.0
10
10
5
5
Returns: 25.0
10
10
4
4
Returns: 24.0
6
2
3
1
Returns: 9.0
6
3
1
2
Returns: -1.0
6
7
1
5
Returns: 437.0
6
10
2
4
Returns: 224.0
7
3
5
2
Returns: 80.0
7
9
2
6
Returns: 612.0
8
4
2
2
Returns: 12.0
9
3
7
0
Returns: -1.0
9
8
6
6
Returns: 396.0
9
6
4
2
Returns: -1.0
10
10
9
8
Returns: -1.0
10
9
1
2
Returns: 869.0
10
10
6
6
Returns: 24.0
7
10
2
5
Returns: 325.0
7
10
1
1
Returns: 69.0
2
4
0
1
Returns: -1.0