boj 65

Description

    champ最近在和dalong玩一个取石子游戏，游戏规则很简单：有三堆石子，两人轮流取，每次任选两堆石子，然后从一堆中取走x（x>=1）个石子，另一堆中取走2*x个石子，最后不能取者输掉游戏，champ每一次都先取。
    现在，champ告诉你初始三堆石子的数量，他想知道，自己是否有必胜的策略。你可以假定champ和dalong都足够聪明，每次都会选择最优的策略。

Input
多组测试数据
每行3个正整数(范围[0,255])，表示最初三堆石子的数量。
0 0 0表示输入结束。这组数据不用处理


Output
每组输出一行
如果champ有必胜策略，那么输出"champ",否则输出"dalong"。(注意，引号不要输出)


Sample Input

1 2 0
1 4 1
0 0 0

Sample Output

champ
dalong

Source
champ

 

 

 

解题：

博弈论问题，规定P状态为后手胜状态，N状态为先手胜状态，对于(0,0,0)为终止状态，当处于终止状态时，先手负，终止状态为P状态。如果对于某一状态(a,b,c)可以按照游戏规则转换为P状态，则当前状态为N状态。而对于P状态，任何符合操作的变换只能到达N状态。

对于此题，通过计算sg[x][y][z](表示某个状态(x,y,z)的sg值)来判断当前状态为P或N状态。

开始的时候，是从上到下构造，计算sg[i][j][k]，结果超时，超时代码：

#include<iostream>
using namespace std;

bool sg[256][256][256];

void exchange(int &i,int &j,int &k)
{
	if(k<j)swap(k,j);
	if(j<i)swap(i,j);
	if(k<j)swap(k,j);
}
int main()
{
	for(int i=0;i<256;i++)
	{
		for(int j=i;j<256;j++)
		{
			for(int k=j;k<256;k++)
			{
				if(j==0)
					sg[i][j][k]=false;//P态，先手赢
				else
				{
					int tmp[3];
					bool flag=false;
					for(int r=1;r<=k;r++)
					{
						for(int p=0;p<3;p++)
						{
							for(int q=p+1;q<3;q++)
							{
								tmp[0]=i;
								tmp[1]=j;
								tmp[2]=k;
								if(tmp[p]>=r&&tmp[q]>=2*r)
								{
									tmp[p]-=r;
									tmp[q]-=2*r;
									exchange(tmp[0],tmp[1],tmp[2]);
									if(sg[tmp[0]][tmp[1]][tmp[2]]==false)
									{
										flag=true;
										break;
									}
								}
								tmp[0]=i;
								tmp[1]=j;
								tmp[2]=k;
								if(tmp[p]>=2*r&&tmp[q]>=r)
								{
									tmp[p]-=2*r;
									tmp[q]-=r;
									exchange(tmp[0],tmp[1],tmp[2]);
									if(sg[tmp[0]][tmp[1]][tmp[2]]==false)
									{
										flag=true;
										break;
									}
								}
							}
							if(flag)
								break;
						}
						if(flag)
							break;
					}
					sg[i][j][k]=flag;
				}
			}
		}
	}
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	while(!(a==0&&b==0&&c==0))
	{
		exchange(a,b,c);
		if(sg[a][b][c])
			printf("champ\n");
		else
			printf("dalong\n");
		scanf("%d%d%d",&a,&b,&c);
	}
}

 

 主要是，对于每个sg[i][j][k],需要计算能否走到P状态，这样从上到下计算，复杂度，很高。可以从下到上计算，对于P状态sg[i][j][k],通过允许操作能到达的sg[i+n][j+2n][k]...等状态均为N状态，其他不能到达的状态即为P状态，简化了计算。AC代码如下：

#include<iostream>
using namespace std;

bool sg[256][256][256];

void exchange(int &i,int &j,int &k)
{
	if(k<j)swap(k,j);
	if(j<i)swap(i,j);
	if(k<j)swap(k,j);
}
int main()
{
	for(int i=0;i<256;i++)
		for(int j=i;j<256;j++)
			for(int k=j;k<256;k++)
				sg[i][j][k]=false;
	for(int i=0;i<256;i++)
	{
		for(int j=i;j<256;j++)
		{
			for(int k=j;k<256;k++)
			{
				if(sg[i][j][k]==false)
				{
					int tmp[3];
					for(int p=0;p<3;p++)
						for(int q=p+1;q<3;q++)
						{
							tmp[0]=i;
							tmp[1]=j;
							tmp[2]=k;
							for(int t=1;tmp[p]+t<256&&tmp[q]+2*t<256;t++)
							{
								tmp[p]+=t;
								tmp[q]+=2*t;
								exchange(tmp[0],tmp[1],tmp[2]);
								sg[tmp[0]][tmp[1]][tmp[2]]=true;
								tmp[0]=i;
								tmp[1]=j;
								tmp[2]=k;
							}
							for(int t=1;tmp[p]+2*t<256&&tmp[q]+t<256;t++)
							{
								tmp[p]+=2*t;
								tmp[q]+=t;
								exchange(tmp[0],tmp[1],tmp[2]);
								sg[tmp[0]][tmp[1]][tmp[2]]=true;
								tmp[0]=i;
								tmp[1]=j;
								tmp[2]=k;
							}
						}
				}
			}
		}
	}
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	while(!(a==0&&b==0&&c==0))
	{
		exchange(a,b,c);
		if(sg[a][b][c])
			printf("champ\n");
		else
			printf("dalong\n");
		scanf("%d%d%d",&a,&b,&c);
	}
}