原题链接
考察:博弈论
思路:
威佐夫博弈,求先手必胜的第一步.
要先手必胜,即把后手面临的局面改为先手必败.当n==(m-n)*k即先手必败.这里分两种情况:
- (m-n)*kd,d<n时,我们可以从n堆里取,但我们需要保证新局面下m,与n的差值不变,才能保证差值*kn
- 从m堆里取,此时m堆的值不可预知,只能枚举判断是否为先手必败.
Code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps = (sqrt(5)+1)/2;
int n,m;
int main()
{
while(scanf("%d%d",&n,&m)!=EOF&&(n+m))
{
if(n>m) swap(n,m);
int d = m-n;
int x = d*eps;
if(x==n) {puts("0"); continue;}
puts("1");
if(x<n) printf("%d %d\n",x,m-n+x);//两堆同时
int t = n;
for(int i=1;i<=m;i++)//从m堆里取
{
int s = m-i;
if(s<t) swap(s,t);//t更小
d = s-t;
x = d*eps;
if(x==t) printf("%d %d\n",min(t,s),max(s,t));
t = n;
}
}
return 0;
}