AT_abc135_e [ABC135E] Golf

题目描述

有一个无限扩展的二维格子。ジャンボ高橋君决定在这个格子上打高尔夫球。

球最初位于原点 $(0,\ 0)$，目标点是格子点（即坐标均为整数的点）$(X,\ Y)$。ジャンボ高橋君每打一杆，可以进行如下操作：

• 从当前球所在的位置，选择一个与当前位置的曼哈顿距离为 $K$ 的格子点，将球击到该点。

当球到达目标点时，游戏结束，所用的击球次数即为得分。ジャンボ高橋君希望用尽可能少的击球次数完成游戏。

请判断是否可以完成游戏。如果可以，请给出一种使得击球次数最小的击球方案。

曼哈顿距离的定义：对于两个坐标 $(x_1,\ y_1),\ (x_2,\ y_2)$，它们的曼哈顿距离为 $|x_1-x_2|+|y_1-y_2|$。

输入格式

输入通过标准输入给出，格式如下：

$K$ $X$ $Y$

输出格式

如果无法完成游戏，输出 -1。

如果可以完成游戏，输出一种使得击球次数最小的击球方案，格式如下：

$s$ $x_1$ $y_1$ $x_2$ $y_2$ $\cdots$ $x_s$ $y_s$

其中，$s$ 是最小得分，$(x_i,\ y_i)$ 表示第 $i$ 杆球击到的坐标。

样例 1

输入

11
-1 2

输出

3
7 4
2 10
-1 2

样例 2

输入

4600
52 149

输出

-1

样例 3

输入

4
9 9

输出

5
1 3
4 2
4 6
6 8
9 9

说明/提示

限制条件

• 所有输入均为整数。
• $1\leq K\leq 10^9$
• $-10^5\leq X,\ Y\leq 10^5$
• $(X,\ Y)\neq (0,\ 0)$

样例解释 1

• $(0,\ 0)$ 到 $(7,\ 4)$ 的曼哈顿距离为 $|0-7|+|0-4|=11$。
• $(7,\ 4)$ 到 $(2,\ 10)$ 的曼哈顿距离为 $|7-2|+|10-4|=11$。
• $(2,\ 10)$ 到 $(-1,\ 2)$ 的曼哈顿距离为 $|2-(-1)|+|10-2|=11$。 由此可见，这种击球方式是正确的。此外，不存在比 $3$ 杆更少的完成方法。

由 ChatGPT 4.1 翻译