TorusSailing | Topcoder Archive

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
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.