由于要输出方案,变得复杂了。数据不是很大,首先打表,所有whthoff 的奇异局势。
然后直接判断是否为必胜局面。
如果必胜,首先判断能否直接同时相减得到。这里不需要遍历或者二分查找。由于两者同时减去一个数,他们的差不变,而且ak=k*(sqrt(5)+1),bk=ak+k;
则可以通过二者的差直接定位,然后判断。
对于另外一种情况,其中一个减去某个数,得到奇异局势,则是分情况二分查找。
注意一些细节
代码如下:
1 #include<stdio.h> 2 #include<cmath> 3 #include<algorithm> 4 #define M 1000002 5 using namespace std; 6 int a[M/2],b[M/2],cnt; 7 void fun1(int n,int m) 8 { 9 int l=0,r=cnt,mid; 10 while(l<=r){ 11 mid=(l+r)>>1; 12 if(n==a[mid]){ 13 if(m>b[mid]) 14 printf("%d %d ",a[mid],b[mid]); 15 return; 16 } 17 if(n>a[mid]) 18 l=mid+1; 19 else r=mid-1; 20 } 21 } 22 void fun2(int n,int m) 23 { 24 int l=0,r=cnt,mid; 25 while(l<=r){ 26 mid=(l+r)>>1; 27 if(n==b[mid]){ 28 if(m>a[mid]) 29 printf("%d %d ",a[mid],b[mid]); 30 return; 31 } 32 if(n>b[mid]) 33 l=mid+1; 34 else r=mid-1; 35 } 36 } 37 int main(){ 38 int n,m,i; 39 for(i=0;i<=1000000;i++){ 40 a[i]=(int)(i*(sqrt(5.0)+1.0)/2.0); 41 b[i]=a[i]+i; 42 if(b[i]>=1000000){ 43 cnt=i; 44 break; 45 } 46 } 47 while(scanf("%d%d",&n,&m)&&(n+m)){ 48 if(n<m) swap(n,m); 49 int t=(int)((n-m)*(sqrt(5.0)+1)/2.0); 50 if(m==t) printf("0 "); 51 else{ 52 printf("1 "); 53 if(n-m<cnt&&m-a[n-m]==n-b[n-m]) 54 printf("%d %d ",a[n-m],b[n-m]); 55 fun1(m,n); 56 if(n!=m) fun1(n,m); 57 fun2(m,n); 58 if(n!=m) fun2(n,m); 59 } 60 } 61 return 0; 62 }