← 返回题目
题库练习 [ABC135E] Golf
← 上一题 下一题 →

A7621 | [ABC135E] Golf

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

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

球最初位于原点 $(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
输出 #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
C++ 编辑器
输入
输出