首页 > 代码库 > UVA - 769 Magic of David Copperfield

UVA - 769 Magic of David Copperfield

题意:著名的魔术师大卫科波菲尔喜欢表演下面的魔术:一个N行N列不同图片的矩阵出现在大屏幕上,我们给所有的图片这样命名:
109. Magic of David Copperfield II 大卫科波菲尔的魔术2(未完成) - Juray - Juray

 

每一个参与的观众被要求将手指放在左上方的图片上(即编号为1的图片),魔术师开始了:魔术师告诉观众在图片上移动k次(移动是把手指放到上下左右相邻的图片上,如果那儿有图片的话),然后他(魔术师)的手微微一指(指向一些图片)并说:“你不在这里”,然后……是真的!你的手指没有指向任何一个被删除的图片(指向的图片)然后再来一次,他告诉观众再移动K2次……以此类推。在最后,他删除到只剩最后一个图片了,然后胜利地微笑着宣布“我抓到你了!”(掌声)。

现在,大卫准备再表演一次这个魔术。不幸的是,他这几天头疼,你知道头疼的时候变戏法有多难!所以你必须写一个程序来帮组大卫变魔术。

 
【输入】输入文件包含一个整数N (1<N<101).
【输出】你的程序需要像下面这样输出数字:
K1 X1,1 X1,2 ... X1,m1
K2 X2,1 X2,2 ... X2,m2
...
Ke Xe,1 Xe,2 ... Xe,me
Ki是观众第i次移动的步数(N<=Ki<=300),所有Ki都要互补不相同(即当i<>j时,满足Ki<>Kj)Xi,1 Xi,2 ... Xi,mi 是在观众进行了Ki次移动之后大卫需要删除的图片(图片数字的顺序是任意的,但是每个图片只能列出一次,并且每回至少删除一张图片)。
每一回的描述都要在一个新行里。每一行的数字都要使用一个或多个空格分隔开。循环了e次之后,只剩下一个图片没有被删除。

思路:构造,洋葱式的一层层删除

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n;

void cal() {
	int cnt = 2*n+1;
	int cur;
	for (int i = 1; i <= n; i++) {
		printf("%d", cnt);
		cnt += 2;
		cur = i;
		for (int j = 1; j <= i; j++) {
			printf(" %d", cur);
			cur += n-1;
		}
		printf("\n");
	}
	int d = n*(n-1)+1;
	for (int i = n-1; i > 1; i--) {
		printf("%d", cnt);	
		cnt += 2;
		cur = d+(n-i);
		for (int j = 1; j <= i; j++) {
			printf(" %d", cur);
			cur -= n-1;
		}
		printf("\n");
	}
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		cal();
		if (t)
			printf("\n");
	}
	return 0;
}