DIFFICULTY:
9999
We will consider several cases.
- A\ge B \implies Yahor wins.
Proof: The strategy for A>B is immediately clear: just decrease the Manhattan distance from Alex by at least 1 after each move. The case A = B is more interesting, and even though it’s still clear how to catch Alex, it’s not very clear how to catch him fast. We will do the general strategy, consisting of 2 parts.
-
Get on the same right-up diagonal as Alex (right up diagonal = set of cells with equal difference of x and y coordinates.
How: Instead of pair (x, y), look at x - y for a while. We have a segment [1 - M, N - 1], and in one move Yahor can move from his cell to any on distance at most A, and Alex to any on distance at most B. It’s easy to see that on segment, Yahor can catch Alex (just go in his direction by A each time, or catch if you can). This will take at most \frac{M+N}{2} iterations (as A \ge 2). -
Get closer to Alex while making sure that you stay on the same right-up diagonal as him after your move.
How: Suppose that currently you (Yahor) are at (x, y), and Alex is at (x+t, y+t) (where t>0), and that Alex moves to x_1, y_1. If x_1\le x, then d((x, y), (x_1, y_1)) = |x - x_1| + |y - y_1| \le (x - x_1) + |y - (y+t)| + |(y+t) - y_1| = (x + t - x_1) + |(y+t) - y_1| =|(x + t) - x_1| + |(y + t) - y_1|, so we would be able to catch Alex immediately. So, x_1 > x. Similarly, y_1>y. Suppose you can’t catch Alex yet. Then, go to the right and to the up as much as possible so that you stay on the same diagonal as him.
It’s easy to see that your x + y will increase in the process. It can’t increase infinitely, so eventually you will catch Alex (in fact, we just showed that we will do this in at most M + N iterations).
- M, N are even, A = \frac{M + N - 2}{2}, B = M + N - 2 \implies Alex wins.
Proof: Alex can jump to any cell, and Yahor can’t get to the opposite corner (largest from him) in one move, so Alex can just choose a safe corner each time.
- min(B, N-1) + min(B, M-1) > 2A \implies Alex wins.
Proof: Let N_1 = min(B, N-1), M_1 = min(B, M - 1). Consider 4 cells (N, M), (N, M - M_1), (N - N_1, M - M_1), (N - N_1, M). They form a rectangle, and Alex can jump from any its corner to any of its two adjacent corners. The distance between two opposite corners is min(B, N-1) + min(B, M-1) > 2A, so there is always a corner which Yahor can’t reach in one jump. Alex can just keep jumping to that corner forever.
- Other cases \implies Yahor wins.
Proof: Wlog N \le M, and we know that A<B, min(B, N-1) + min(B, M-1) \le 2A. If B \le N-1, we immediately get min(B, N-1) + min(B, M-1) = 2B > 2A, so it’s not the case. In addition, 2A \ge min(B, N-1) + min(B, M-1) \ge 2min(B, N-1) = 2(N-1), so A \ge N-1.
If B\ge M-1, then we get 2A \ge (N - 1) + (M - 1). In this case, if Yahor stands in (\lfloor \frac{N+1}{2} \rfloor, \lfloor \frac{M+1}{2} \rfloor), he is able to move to any cell of the grid at all, unless N, M are even and A = \frac{N+M-2}{2}. In that case, he is able to move to any cell except of (N, M). As B \neq N+M-2, Yahor can now catch Alex after moving to (\lceil \frac{N+1}{2} \rceil, \lceil \frac{M+1}{2} \rceil), as the only safe cell now is (1, 1), and Alex won’t be able to get there.
Now, we assume that N - 1 \le B < M - 1, and N - 1 + B \le 2A.
Yahor will begin by moving to the cell (\lfloor \frac{N+1}{2} \rfloor, 1). We will try to support the following invariant: Alex is always to the right of Yahor. In the i-th next iteration, Yahor will move to (\lfloor \frac{N+1}{2} \rfloor, i) or (\lceil \frac{N+1}{2} \rceil, i).
Wlog Yahor now is at (\lfloor \frac{N+1}{2} \rfloor, i), and after the move of Alex, he is to the right of Yahor, in cell (x, y). If we can’t catch him, we must have |x - \lfloor \frac{N+1}{2} \rfloor| + (y - i) > A, so y - (i+1) \ge A - \lfloor \frac{N}{2} \rfloor. Now, if A > \frac{N}{2}, move to (\lceil \frac{N+1}{2} \rceil, i+1), else move to (\lfloor \frac{N+1}{2} \rfloor, i+1).
Wlog A \le \frac{N}{2}, so we move to (\lfloor \frac{N+1}{2} \rfloor, i+1). Can Alex move to the left of Yahor and not be immediately caught? Turns out, no. Suppose that he moves to (x_1, y_1). Clearly, (i +1) - y_1 = (y - y_1) - (y - (i+1)) \le B - (A - \lfloor \frac{N}{2} \rfloor) , and |\lfloor \frac{N+1}{2} \rfloor - x_1| \le \lfloor \frac{N}{2} \rfloor. So, after adding we get that distance to (x_1, y_1) is at most B + 2\lfloor \frac{N}{2} \rfloor - A. When is this >A? When 2A< B + 2\lfloor \frac{N}{2} \rfloor. But we know that 2A\ge N - 1 + B. The only case when we can’t immediately catch then is when N is even, and both inequalities are equalities, but this would mean y - y_1 = B, so x_1 would have to equal x, which isn’t possible, as |\lfloor \frac{N+1}{2} \rfloor - x| \le \lfloor \frac{N-1}{2} \rfloor. The end!