1122.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1122 on 2006-08-19 at 23:27:59 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int B = 19;
const int S = 1 << B;

int g[S], seq[B], sn;

int erase(int, int);
int move(int, int);

int main()
{
	int n;

	memset(g, -1, sizeof(g));
	for(int t = 1; scanf("%d", &n) != EOF && n != 0; t++) {
		int st = sn = 0;
		for(int i = 0; i < n; i++) {
			int a; scanf("%d", &a);
			st |= 1 << (a-2);
		}
		move(st, 0);
		printf("Test Case #%d\n", t);
		if(sn == 0) printf("There's no winning move.");
		else {
			printf("The winning moves are:");
			for(int i = 0; i < sn; i++) printf(" %d", seq[i]);
		}
		printf("\n\n");
	}
	
	return 0;
}

int erase(int st, int m)
{
	st ^= 1 << (m-2);
	for(int i = 0; i+m <= B; i++)
		if(!(st&(1<<i)) && (st&(1<<(m+i)))) st ^= 1 << (m+i);
	return st;
}
int move(int st, int d)
{
	if(d == 0 || g[st] == -1) {
		for(int i = 0; i < B; i++) {
			if(!(st&(1<<i))) continue;
			int nst = erase(st, i+2), r = move(nst, d+1);
			if(d == 0 && r == 0) seq[sn++] = i+2;
			if(r == 0) g[st] = 1;
		}
		if(g[st] != 1) g[st] = 0;
	}
	return g[st];
}