CF1989A Catch the Coin 题解

题意简述

平面网格上有 $n$ 个硬币，第 $i$ 个硬币初始坐标为 $(x_i, y_i)$，且都不在原点 $(0,0)$。Monocarp 初始在 $(0,0)$。

每一回合：

1. Monocarp 可以向八方向（上下左右及四对角）移动一步；
2. 如果移动后到达某个硬币所在坐标，则立即收集该硬币；
3. 之后所有未收集的硬币向下移动一格（$y$ 减 1）。

问对于每个硬币，Monocarp 是否能收集到它。

---

关键观察

设 Monocarp 在第 $t$ 步移动后收集到硬币（$t \ge 1$）。在第 $t$ 步移动前，硬币已经下落了 $t-1$ 次，其坐标为 $(x,\ y - (t-1))$。Monocarp 移动后到达的位置必须恰好是这个坐标，才能收集。

因此，存在整数 $t \ge 1$ 使 Monocarp 能在 $t$ 步内从 $(0,0)$ 移动到 $(x,\ y - t + 1)$。

在八方向规则下，$t$ 步能到达的坐标 $(X,Y)$ 满足 $\max(|X|,|Y|) \le t$（切比雪夫距离 $\le t$）。

于是条件为：

$$\max(|x|,\ |y - t + 1|) \le t$$

即同时满足：

$$|x| \le t \qquad \text{和} \qquad |y - t + 1| \le t $$

---

化简条件

由 $|y - t + 1| \le t$ 展开：

$$-t \le y - t + 1 \le t$$

左半边：$-t \le y - t + 1 \ \Longrightarrow\ y + 1 \ge 0 \ \Longrightarrow\ y \ge -1$。

右半边：$y - t + 1 \le t \ \Longrightarrow\ y + 1 \le 2t$。由于 $t$ 可以取任意大整数，只要 $y \ge -1$，总可以取足够大的 $t$ 满足 $t \ge |x|$ 且 $t \ge (y+1)/2$，即存在可行步数。

结论：能够收集硬币 当且仅当 $y \ge -1$。

---

构造方案

若 $y \ge -1$，可这样构造 $t$：

1. 先取 $t_0 = |x|$（至少需要这么多步来调整水平坐标）。
2. 再取 $t = \max(t_0,\ y+1)$（如果 $y+1 \le 0$ 则 $t = t_0$）。

可以验证 $\max(|x|, |y - t + 1|) \le t$ 成立。于是 Monocarp 能在 $t$ 步内移动到硬币所在位置并收集。

---

代码实现

只需读入每个 $(x,y)$，判断 $y \ge -1$：

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, x, y;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x >> y;
        // 通过推导可知：能抓到当前硬币当且仅当 y >= -1
        if (y >= -1)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}