199A - Hexadecimal's theorem

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].

199B - Special Olympics

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 R1 and R2 to denote the other two circles that form a ring, with R1 < R2. Then, the circle r forms a “full” one if any of the three conditions are satisfied.

1) r is completely outside R2;

2) r is completely inside R1;

3) R2 is completely inside r.

199C - About Bacteria

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₀, a₁, a₂, ..., 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₀, b₁, ..., b_m, where b₀ = t and b_i + 1 = kb_i + b, and one can check that a_i ≤ b₀ < a_i + 1 ≤ b₁ < a_i + 2 ≤ b₂.... Therefore, we only need check that which segment does t fall into.

199D - Jumping on Walls

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.

199E - Delivering Carcinogen

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 .