E - Golf 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点: 500 点

問題文

無限に広がる二次元格子があります。ジャンボ高橋君はこの上でゴルフをすることにしました。

ボールははじめ原点 (0, 0) にあり、ゴールは格子点(座標がいずれも整数である点) (X, Y) です。ジャンボ高橋君は 1 打ごとに、次の操作を行えます。

  • その時点でボールがある点とのマンハッタン距離が K であるような格子点を 1 つ選び、その点にボールを飛ばす。

ゴールと同じ座標にボールが来た時点でクリアとなり、それまでの打数がスコアとなります。ジャンボ高橋君はできるだけ少ないスコアでクリアしたいと思っています。

クリアが可能かどうか判定し、可能ならばスコアが最小となるボールの動かし方を 1 つ求めてください。

マンハッタン距離の説明

2 つの座標 (x_1, y_1), (x_2, y_2) に対するマンハッタン距離は、|x_1-x_2|+|y_1-y_2| と定義されます。

制約

  • 入力はすべて整数
  • 1 \leq K \leq 10^9
  • -10^5 \leq X, Y \leq 10^5
  • (X, Y) \neq (0, 0)

入力

入力は以下の形式で標準入力から与えられます。

K
X Y

出力

クリアが不可能な場合は -1 と出力してください。

クリアが可能な場合、スコアが最小となるボールの動かし方を次のように出力してください。

s
x_1 y_1
x_2 y_2
.
.
.
x_s y_s

ここで、s はスコアの最小値です。また、(x_i, y_i) を i 打目にボールを飛ばす先の座標とします。

入力例 1

11
-1 2

出力例 1

3
7 4
2 10
-1 2
  • (0, 0), (7, 4) のマンハッタン距離は |0-7|+|0-4|=11。
  • (7, 4), (2, 10) のマンハッタン距離は |7-2|+|4-10|=11。
  • (2, 10), (-1, 2) のマンハッタン距離は |2-(-1)|+|10-2|=11。

以上より、このボールの動かし方は正しいです。

また、3 打より少なくクリアする方法は存在しません。

入力例 2

4600
52 149

出力例 2

-1

入力例 3

4
9 9

出力例 3

5
1 3
4 2
4 6
6 8
9 9

Score : 500 points

Problem Statement

Jumbo Takahashi will play golf on an infinite two-dimensional grid.

The ball is initially at the origin (0, 0), and the goal is a grid point (a point with integer coordinates) (X, Y). In one stroke, Jumbo Takahashi can perform the following operation:

  • Choose a grid point whose Manhattan distance from the current position of the ball is K, and send the ball to that point.

The game is finished when the ball reaches the goal, and the score will be the number of strokes so far. Jumbo Takahashi wants to finish the game with the lowest score possible.

Determine if the game can be finished. If the answer is yes, find one way to bring the ball to the goal with the lowest score possible.

What is Manhattan distance?

The Manhattan distance between two points (x_1, y_1) and (x_2, y_2) is defined as |x_1-x_2|+|y_1-y_2|.

Constraints

  • All values in input are integers.
  • 1 \leq K \leq 10^9
  • -10^5 \leq X, Y \leq 10^5
  • (X, Y) \neq (0, 0)

Input

Input is given from Standard Input in the following format:

K
X Y

Output

If the game cannot be finished, print -1.

If the game can be finished, print one way to bring the ball to the destination with the lowest score possible, in the following format:

s
x_1 y_1
x_2 y_2
.
.
.
x_s y_s

Here, s is the lowest score possible, and (x_i, y_i) is the position of the ball just after the i-th stroke.

Sample Input 1

11
-1 2

Sample Output 1

3
7 4
2 10
-1 2
  • The Manhattan distance between (0, 0) and (7, 4) is |0-7|+|0-4|=11.
  • The Manhattan distance between (7, 4) and (2, 10) is |7-2|+|4-10|=11.
  • The Manhattan distance between (2, 10) and (-1, 2) is |2-(-1)|+|10-2|=11.

Thus, this play is valid.

Also, there is no way to finish the game with less than three strokes.

Sample Input 2

4600
52 149

Sample Output 2

-1

Sample Input 3

4
9 9

Sample Output 3

5
1 3
4 2
4 6
6 8
9 9