← 返回题目列表

Codeforces · 1667/C

C. 半皇后封面

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

为您提供一个包含 $$$n$$$ 行和 $$$n$$$ 列的板,编号从 $$$1$$$ 到 $$$n$$$。第 $$$a$$$ 行和第 $$$b$$$ 列的交集由 $$$(a, b)$$$ 表示。

半皇后攻击同一行、同一列和一条对角线上的单元格。更正式地说,如果 $$$a=c$$$ 或 $$$b=d$$$ 或 $$$a-b=c-d$$$,$$$(a, b)$$$ 上的半皇后会攻击单元 $$$(c, d)$$$。

蓝色细胞受到攻击。

构建最优解决方案。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 棋盘的大小。

输出

在第一行中打印一个整数 $$$k$$$ — 半皇后的最小数量。

在接下来的 $$$k$$$ 行中,打印两个整数 $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — 第 $$$i$$$ 半皇后的位置。

如果有多个解决方案,请打印其中一个。

示例

输入 #1

1

输出 #1

1
1 1

输入 #2

2

输出 #2

1
1 1

输入 #3

3

输出 #3

2
1 1
1 2

注意

示例$$$1$$$:一个半皇后就足够了。注意:$$$(1, 1)$$$ 上的半皇后会攻击 $$$(1, 1)$$$。

示例$$$2$$$:一个半皇后也足够了。 $$$(1, 2)$$$ 或 $$$(2, 1)$$$ 将是错误的解决方案,因为 $$$(1, 2)$$$ 上的半皇后不会攻击单元格 $$$(2, 1)$$$,反之亦然。 $$$(2, 2)$$$ 也是一个有效的解决方案。

示例$$$3$$$:不可能用一个半皇后覆盖棋盘。 $$$2$$$ 半皇后有多种解决方案;您可以打印其中任何一个。