TorusSailing
SRM 614 · 2013-12-22 · by EmK
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.
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).
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
Submissions are judged against all 140 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TorusSailing with a public method double expectedTime(int N, int M, int goalX, int goalY) · 140 test cases · 2 s / 256 MB per case