← 返回题目列表

Codeforces · 1173/B

B. Nauuo 和国际象棋

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

Nauuo是一个喜欢下棋的女孩。

有一天,她自己发明了一种游戏,需要$$$n$$$棋子才能在$$$m\times m$$$棋盘上下棋。行和列的编号从 $$$1$$$ 到 $$$m$$$。我们将第 $$$r$$$ 行和第 $$$c$$$ 列的交叉点上的单元格表示为 $$$(r,c)$$$。

游戏的目标是将编号从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 棋子放置在棋盘上,第 $$$i$$$ 棋子位于 $$$(r_i,\,c_i)$$$ 上,同时满足以下规则:对于所有棋子对 $$$i$$$ 和 $$$j$$$, $$$|r_i-r_j|+|c_i-c_j|\ge|i-j|$$$。这里$$$|x|$$$表示$$$x$$$的绝对值。

然而,Nauuo发现,有时她找不到解决办法,因为棋盘太小了。

她想找到最小的棋盘,可以根据规则放置 $$$n$$$ 个棋子。

她还想知道如何将棋子放在这样的棋盘上。你能帮助她吗?

输入

唯一的一行包含一个整数 $$$n$$$ ($$$1\le n\le 1000$$$) — 游戏的棋子数量。

输出

第一行包含一个整数 - $$$m$$$ 的最小值,其中 $$$m$$$ 是合适棋盘的边长。

接下来的 $$$n$$$ 行的第 $$$i$$$ 包含两个整数 $$$r_i$$$ 和 $$$c_i$$$ ($$$1\le r_i,c_i\le m$$$) — 第 $$$i$$$ 棋子的坐标。

如果有多个答案,请打印其中一个。

示例

输入 #1

2

输出 #1

2
1 1
1 2

输入 #2

4

输出 #2

3
1 1
1 3
3 1
3 3

注意

在第一个示例中,如果不违反规则,则无法将两个棋子放在 $$$1\times1$$$ 棋盘上。但是你可以将两颗棋子放在 $$$2\times2$$$ 棋盘上,如下所示:

在第二个示例中,您不能在 $$$2\times2$$$ 棋盘上放置四个棋子而不违反规则。例如,如果您像这样放置碎片:

则 $$$|r_1-r_3|+|c_1-c_3|=|1-2|+|1-1|=1$$$, $$$|1-3|=2$$$, $$$1<2$$$;和 $$$|r_1-r_4|+|c_1-c_4|=|1-2|+|1-2|=2$$$、$$$|1-4|=3$$$、$$$2<3$$$。它不满足规则。

但是,在 $$$3\times3$$$ 棋盘上,您可以像这样放置四个棋子: