D - ぶどうの教室 解説 /

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

配点 : 400 点

問題文

プリンセスの高橋さんは武道を習うつもりでしたが、間違えて葡萄の教室に来てしまいました。

N 段にわたって、ブドウの粒が三角形状に並んでいます。上から i 段目には N-i+1 個の粒があり、左から j 番目の粒を (i,j) と表します。

粒 (i,j) と、次に挙げる粒は、その座標が存在するとき隣り合っています。

  • (i,j-1),(i,j+1)
  • (i-1,j),(i-1,j+1)
  • (i+1,j-1),(i+1,j)

たとえば N = 4 のときは下図のようになっています。

高橋さんは、隣り合う 2 粒を選んで食べる操作を繰り返します。一度食べた粒を再び選ぶことはできません。

行うことのできる操作回数の最大値を求め、その回数の操作方法を 1 つ出力してください。

制約

  • 1 \le N \le 1000
  • 入力はすべて整数である

入力

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

N

出力

操作回数の最大値を Q とする。一行目に Q を出力せよ。

続く Q 行のうち k 行目 (1 \le k \le Q) には、k 回目の操作で選ぶ 2 粒の座標を次の形式で出力せよ。

x_1 y_1 x_2 y_2

これは、粒 (x_1,y_1) と粒 (x_2,y_2) を選んで食べることを表す。出力する各組について、次の条件をすべて満たさなければならない。

  • 粒 (x_1,y_1) と粒 (x_2,y_2) は隣り合っている。
  • 同じ粒が複数の組に含まれない。

条件を満たす出力が複数存在する場合、どれを出力してもよい。

入力例 1

3

出力例 1

3
1 1 1 2
1 3 2 2
3 1 2 1

ブドウは 6 粒あります。図のように組にして、すべての粒を一度ずつ選ぶことで 3 回の操作を行えます。

入力例 2

2

出力例 2

1
1 2 2 1

ブドウは 3 粒あります。1 粒は食べることができません。

入力例 3

4

出力例 3

5
1 1 1 2
2 2 2 1
3 1 4 1
1 4 1 3
3 2 2 3