acm 항 저 우 전기 HDU 2177 취 (2 더미) 돌 게임 (위 조 프 게임)

제목 주소:http://acm.hdu.edu.cn/showproblem.php?pid=2177
돌멩이 놀이
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2606    Accepted Submission(s): 1582
Problem Description
두 무더기 의 돌 이 있 는데, 수량 이 임의로 다 를 수 있다.게임 은 두 사람 이 돌아 가면 서 돌 을 채취 하기 시작 했다.게임 규정 에 따 르 면 매번 두 가지 서로 다른 취 법 이 있 는데 하 나 는 임의의 한 무더기 에서 임의의 많은 돌 을 가 져 갈 수 있다.둘 째 는 두 더미 에서 같은 양의 돌 을 동시에 가 져 갈 수 있다.마지막 으로 돌 을 모두 가 져 온 자가 승자 다.지금 은 최초의 두 무더기 의 돌 수 를 제시 합 니 다. 만약 당신 이 먼저 취 할 차례 라면 쌍방 이 모두 가장 좋 은 전략 을 취한 다 고 가정 하고 마지막 에 당신 이 승자 인지 패자 인지 물 어보 세 요.만약 네가 이기 면, 너 는 첫 번 째 로 어떻게 자식 을 얻 니?
 
Input
몇 줄 을 포함 하 는 지 입력 하면 몇 가지 돌의 초기 상황 을 나타 낸다. 그 중에서 한 줄 에 두 개의 부정 정수 a 와 b 를 포함 하고 두 개의 돌의 수 를 나타 낸다. a 와 b 는 모두 1, 000, 000 보다 크 지 않 고 a < = b.a = b = 0 종료.
 
Output
출력 도 몇 줄 이 있 습 니 다. 마지막 에 당신 이 패자 라면 0 입 니 다. 반대로 1 을 출력 하고 당신 을 이 긴 당신 이 첫 번 째 로 돌 을 뽑 은 후에 남 은 두 무더기 의 돌 수량 x, y, x < = y 를 출력 합 니 다.만약 에 임의의 한 무더기 에서 돌 을 가 져 가면 이 길 수 있 고 두 무더기 에서 같은 수량의 돌 을 동시에 가 져 가도 이 길 수 있다. 먼저 같은 수량의 돌 을 가 져 가 는 상황 을 수출 한다.
 
Sample Input

 
   

     1 2 5 8 4 7 2 2 0 0 
   
 
  

分析：

此题是一个威佐夫博弈的巩固版，要求判断出输赢后，输出第一次的取法。

比较蛮力的办法，枚举

威佐夫博弈解释：http://blog.csdn.net/winter2121/article/details/71810375

代码：

#include
#include
const double eqa=(1+sqrt(5.0))/2.0;
int main()
{
	int a,b;
	while(~scanf("%d%d",&a,&b),a&&b)
	{ 
		if(a>b)
		{
			a=a^b;
			b=a^b;
			a=a^b;
		}
		int k=b-a;
		if(a==(int)(k*eqa))
			puts("0");//     ，  
		else
		{
			puts("1");
			for(int j=1;j<=a;j++)//        j 
			{
				int ak=a-j;
				int bk=b-j;
				if(ak==(int)((bk-ak)*eqa))
				{
					printf("%d %d
",ak,bk);
					break;
				}
			}
			int at=0,bt=0;
			for(int j=1;jbk)
{
int temp=ak;
ak=bk;
bk=temp;
}
if(ak==(int)((bk-ak)*eqa)&&ak!=at&&bk!=bt)
{
printf("%d %d",ak,bk);
break;
}
}
}
}
return 0;
}