← 返回题目列表

AtCoder · relay_j

J. 连接棋盘

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

我们有一个 N×N 棋盘。

从左上角的正方形开始,有一个正方形 i 右边的方块和 下面的 j 方块表示为 (i, j)。特别地,左上角的正方形表示为 (0, 0).

每个方格 (i, j) 这样 i+j 是偶数,为黑色,其他方格为白色。

我们通过绘制一些白色方块来满足以下条件:

  • 从方块可以到达任何黑色方块 (0, 0) 通过重复移动到与当前方块共享一条边的黑色方块。

最多通过绘画达到目的 170000 黑色方块。

约束

  • 1 \leq N \leq 1,000

输入

输入由标准输入按以下格式给出:

N

输出

按以下格式打印要绘制的方块:

K
x_1 y_1
x_2 y_2
:
x_K y_K

这意味着总共 K 方块被漆成黑色, i- 其中第一个是 (x_i, y_i).

判断

仅当满足以下所有条件时,输出才被视为正确:

  • 0 \leq K \leq 170000
  • 0 \leq x_i, y_i \leq N-1
  • 对于每个 i, x_i + y_i 是奇数。
  • If i \neq j,那么 (x_i, y_i) \neq (x_j, y_j).
  • 通过绘制所有指定的方块来满足语句中的条件。 您将获得一块

示例输入 1

2

示例输出 1

1
1 0

示例输入 2

4

示例输出 2

3
0 1
2 1
2 3