P2041 分裂游戏
题目描述
有一个无限大的棋盘,棋盘左下角有一个大小为 n 的阶梯形区域,其中最左下角的那个格子里有一枚棋子。你每次可以把一枚棋子“分裂”成两枚棋子,分别放在原位置的上边一格和右边一格。(但如果目标位置已有棋子,则不能这样做)你的目的是通过有限次的操作,让整个阶梯里不再有任何棋子。下图所示的是 n = 2 时的一种解法。
我们用从下往上数的方式标记行,从左往右数的方式标记列,以(行,列)来标记棋子,并且都从1开始。
例如,第三步中的三个棋子坐标分别为(3,1),(2,2),(1,2)
现在已知n,你需要做的是给出合适的操作序列。
输入输出格式
输入格式:
输入只有一行,这一行只包含一个正整数n,其意义如题目所述。
输出格式:
如果有解,第一行应包含一个正整数m,表示总共需要的操作步数。
以下m行,每行包括两个正整数xi,yi,表示第i步操作分裂的是处于第xi行第yi列的棋子。
如果无解,只需在第一行输出-1。
输入输出样例
输入样例1
1
输出样例1
1
1 1
输入样例2
2
输出样例2
4
1 1
2 1
2 2
1 2
说明
↖(ω)↗加油!
对于40%的数据:N≤8;
对于100%的数据:N≤1000。
说实话,这题太诡异了
玩了好久愣是没把n=3的情况弄出来,心想不会只有1,2有解吧
然后去看题解了
结果真是。。
转一下详细证明吧
Code:
#include <cstdio>
int main()
{
int n;
scanf("%d",&n);
if(n==1) printf("1\n1 1\n");
else if(n==2) printf("4\n1 1\n2 1\n2 2\n1 2\n");
else printf("-1\n");
return 0;
}
2018.9.6