#P2041. 分裂游戏

分裂游戏

题目描述

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

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

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

现在已知 nn,你需要做的是给出合适的操作序列。

输入格式

输入一个正整数 nn

输出格式

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

以下 mm 行,每行包括两个正整数 xi,yix_i,y_i,表示第 ii 步操作分裂的是处于第 xix_i 行第 yiy_i 列的棋子。

如果无解,只需在第一行输出 1-1

1
1
1 1
2
4
1 1
2 1
2 2
1 2

提示

  • 对于 40%40\% 的数据:n8n \leq 8
  • 对于 100%100\% 的数据:n1000n \leq 1000