首页 > 代码库 > 取(2堆)石子游戏（杭电2177）

取(2堆)石子游戏（杭电2177）

2024-07-29 07:58:18   221人阅读

取(2堆)石子游戏

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1175    Accepted Submission(s): 706


Problem Description
有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。如果你胜，你第1次怎样取子? 
 

Input
输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000，且a<=b。a=b=0退出。
 

Output
输出也有若干行，如果最后你是败者，则为0，反之，输出1，并输出使你胜的你第1次取石子后剩下的两堆石子的数量x,y,x<=y。如果在任意的一堆中取走石子能胜同时在两堆中同时取走相同数量的石子也能胜，先输出取走相同数量的石子的情况.
 

Sample Input
1 2 
5 8
4 7
2 2
0 0
 

Sample Output
0
1
4 7
3 5
0
1
0 0
1 2
/*本题还是威佐夫博弈。
利用重要性质：任何自然数都包含在一个且仅有一个奇异局势中。
奇异局势即必败点，想要理解威佐夫博弈，在百度文库博弈入门有详细解释 
*/
/*核心思路：以ｍ［ｋ］，ｎ［ｋ］为界限来分析，就是3种情况
（１）如果ａ＞ｍ［ｋ］，ｂ＞ｎ［ｋ］，自然的剩下的石子数量就是ａ［ｋ］,ｂ［ｋ］；
（２）如果ａ＜ｍ［ｋ］（ｂ＜ｎ［ｋ］），然后你就需要在ｍ［ｋ］之前寻找是不是有ｍ［ｉ］或者ｂ［ｉ］和ａ相等，
是不是有ｍ［ｉ］或者ｎ［ｉ］和ｂ相等，当然了有的情况是不需要考虑的因为是不可能出现的。
（３），如果ａ＝ｍ［ｋ］，那么你就挂了。
*/
#include<stdio.h>
#include<math.h>
int a[1000010];
int b[1000010];
int main()
{
	int m,n,t,k,i;
    a[0]=0,b[0]=0;
    a[1]=2,b[1]=1;
	for(i=2;i<1000010;i++) //先打表。 
	{
		b[i]=i*(1+sqrt(5))/2;
		a[i]=b[i]+i;
	}
	while(scanf("%d %d",&m,&n)!=EOF&&(m+n))
	{
		if(m<n);
		{
			t=m;m=n;n=t;
		}
		k=m-n;
		if(n==b[k])
		{
		   printf("0\n");
		   continue;
	    }
		else  //核心思路的代码。 
		{
		    printf("1\n");
		    if(n<b[k])
		    {
		    	for(i=1;i<n;i++){
		    	if(n==b[i]&&m>a[i])
		    	printf("%d %d\n",b[i],a[i]);
		    	if(m==a[i]&&n>b[i])
		    	printf("%d %d\n",b[i],a[i]);
		    	}
		    }
		    if(n>b[k])
		    {
		    	printf("%d %d\n",b[k],a[k]);
		    	for(i=1;i<n;i++)
		        {
		        	if(n==a[i]&&m>b[i])
		        	printf("%d %d\n",b[i],a[i]);
		        	if(n==b[i]&&m>a[i])
		        	printf("%d %d\n",b[i],a[i]);
		        }   
		    }
	   }
    }  
	return 0;
}


取(2堆)石子游戏（杭电2177）


联系
我们