A7621. [ABC135E] Golf
编程题
提高+/省选-
知识点
题目描述
有一个无限扩展的二维格子。ジャンボ高橋君决定在这个格子上打高尔夫球。
球最初位于原点 $(0,\ 0)$，目标点是格子点（即坐标均为整数的点）$(X,\ Y)$。ジャンボ高橋君每打一杆，可以进行如下操作：
- 从当前球所在的位置，选择一个与当前位置的曼哈顿距离为 $K$ 的格子点，将球击到该点。
当球到达目标点时，游戏结束，所用的击球次数即为得分。ジャンボ高橋君希望用尽可能少的击球次数完成游戏。
请判断是否可以完成游戏。如果可以，请给出一种使得得分最小的击球方案。
曼哈顿距离的定义：对于两个坐标 $(x_1,\ y_1),\ (x_2,\ y_2)$，它们的曼哈顿距离为 $|x_1-x_2|+|y_1-y_2|$。
球最初位于原点 $(0,\ 0)$，目标点是格子点（即坐标均为整数的点）$(X,\ Y)$。ジャンボ高橋君每打一杆，可以进行如下操作：
- 从当前球所在的位置，选择一个与当前位置的曼哈顿距离为 $K$ 的格子点，将球击到该点。
当球到达目标点时，游戏结束，所用的击球次数即为得分。ジャンボ高橋君希望用尽可能少的击球次数完成游戏。
请判断是否可以完成游戏。如果可以，请给出一种使得得分最小的击球方案。
曼哈顿距离的定义：对于两个坐标 $(x_1,\ y_1),\ (x_2,\ y_2)$，它们的曼哈顿距离为 $|x_1-x_2|+|y_1-y_2|$。
输入格式
输入通过标准输入给出，格式如下：
> $K$ $X$ $Y$
> $K$ $X$ $Y$
输出格式
如果无法完成游戏，输出
如果可以完成游戏，输出一种使得得分最小的击球方案，格式如下：
> $s$ $x_1$ $y_1$ $x_2$ $y_2$ $\cdots$ $x_s$ $y_s$
其中，$s$ 是最小得分，$(x_i,\ y_i)$ 表示第 $i$ 杆球击到的坐标。
-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
输出 #1
3 7 4 2 10 -1 2
输入 #2
4600 52 149
输出 #2
-1
输入 #3
4 9 9
输出 #3
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$ 杆更少的完成方法。
- 所有输入均为整数。
- $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$ 杆更少的完成方法。