We use *f*[*n*] to denote the *n*-th Fibonacci integer, and thus *f*[*n*] = *f*[*n* - 1] + *f*[*n* - 2] = *f*[*n* - 2] + *f*[*n* - 3] + *f*[*n* - 2].

There are four circles, and we are going to check each of them to see whether it forms a “full” circle or not. We use *r* to denote the current circle that we are considering, and use *R*1 and *R*2 to denote the other two circles that form a ring, with *R*1 < *R*2. Then, the circle *r* forms a “full” one if any of the three conditions are satisfied.

1) *r* is completely outside *R*2;

2) *r* is completely inside *R*1;

3) *R*2 is completely inside *r*.

We can find that . Then, we can construct an inequality, and compute the answer.

Another solution is that suppose we substitute *x* = 1 to the function, and calculate *a*_{i} = *f*(*i*, 1). Then, *a*_{0}, *a*_{1}, *a*_{2}, ..., *a*_{n} forms an increasing sequence, and *a*_{i + 1} = *ka*_{i} + *b*. Assume that *a*_{i} ≤ *t* < *a*_{i + 1}, then we need *n* - *i* steps to obtain a value that is no less than *a*_{n} = *z*. The reason is simple, since this is an increasing function. For an intuitive understanding, we can generate another sequence starting with *b*_{0}, *b*_{1}, ..., *b*_{m}, where *b*_{0} = *t* and *b*_{i + 1} = *kb*_{i} + *b*, and one can check that *a*_{i} ≤ *b*_{0} < *a*_{i + 1} ≤ *b*_{1} < *a*_{i + 2} ≤ *b*_{2}.... Therefore, we only need check that which segment does *t* fall into.

This is in fact a shortest path problem. We can simply adopt the SPFA (shortest path faster algorithm) framework, and calculate the minimum distance (in fact it is “minimum time”) from the starting point to any other one. Be careful that when we update the minimum distance, we should consider the current “water level” as an extra condition, i.e., we can only update the minimum distance if all the corresponding positions are still safe. The player can escape successfully if he can reach any position that is larger than *n*.

The main idea is to implement binary search to calculate the time, and the remaining work is to determine whether one can catch the other one within the time *t*, which we are currently testing.

We first compute for player 1 the position that he can reach after time *t*. Then, we check whether the second player can catch him at that position or not. Then, we will face the following problem. Given two points A and B strictly outside the circle, what is the shortest distance between them?

If the straight line connecting them has no common points with the circle, then their distance is just the length of line. Otherwise, we draw their tangent lines starting from A and B to the circle, respectively, with intersecting points a and b. Then, the answer is the length of Aa, plus the length of Bb, plus the length of bow .