← 返回题目
题库练习 分裂游戏
← 上一题 下一题 →

A1992 | 分裂游戏

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

有一个无限大的棋盘，棋盘左下角有一个大小为 $n$ 的阶梯形区域，其中最左下角的那个格子里有一枚棋子。你每次可以把一枚棋子“分裂”成两枚棋子，分别放在原位置的上边一格和右边一格。（但如果目标位置已有棋子，则不能这样做）你的目的是通过有限次的操作，让整个阶梯里不再有任何棋子。下图所示的是 $n = 2$ 时的一种解法。

![](/uploads/acgo/image/4923bd14fad9cd3f_08ef80d40c7b.png)

我们用从下往上数的方式标记行，从左往右数的方式标记列，以 (行,列) 来标记棋子，并且都从 $1$ 开始。

例如，第三步中的三个棋子坐标分别为 $(3,1),(2,2),(1,2)$。

现在已知 $n$，你需要做的是给出合适的操作序列。

输入格式

输入一个正整数 $n$。

输出格式

如果有解，第一行应包含一个正整数 $m$，表示总共需要的操作步数。

以下 $m$ 行，每行包括两个正整数 $x_i,y_i$，表示第 $i$ 步操作分裂的是处于第 $x_i$ 行第 $y_i$ 列的棋子。

如果无解，只需在第一行输出 $-1$。

输入输出样例

输入 #1
1
输出 #1
1
1 1
输入 #2
2
输出 #2
4
1 1
2 1
2 2
1 2
C++ 编辑器
输入
输出