1532.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1532 on 2006-07-06 at 12:59:15 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int S = 5*5*5*5*5*5;
const char PLAYER[] = "BA";
const int F[] = { 1, 5, 5*5, 5*5*5, 5*5*5*5, 5*5*5*5*5 };
const int LMT = 31;

int st[S], wn, cn[6];

int play(int, int, int);

int main()
{
	char pile[64];
	int i;

	while(gets(pile) != NULL) {
		for(i = 0; i < 6; i++) cn[i] = 4;
		memset(st, -1, sizeof(st));
		int total = 0, code = 0;
		for(i = 0; pile[i] != 0; i++) { cn[pile[i]-'1']--; total += pile[i]-'0'; }
		wn = i&1;
		for(i = 0; i < 6; i++) code += cn[i]*F[i];
		printf("%s %c\n", pile, PLAYER[play(code, total, wn)^wn]);
	}
	
	return 0;
}

int play(int code, int sum, int n)
{
	if(st[code] != -1) {}
	else if(sum > LMT) st[code] = (n == wn);
	else {
		int i; st[code] = (n != wn);
		for(i = 0; i < 6; i++) {
			if(cn[i] == 0) continue;
			cn[i]--;
			int r = play(code-F[i], sum+i+1, !n);
			cn[i]++;
			if(n == wn && r) { st[code] = 1; break; }
			else if(n != wn && !r) { st[code] = 0; break; }
		}
	}
	return st[code];
}