【HDOJ】1525 Euclid's Game

自己想明白的第一道博弈。
首先a==b的时候肯定是先手赢;

然后当a>=2*b时,不妨假设a=nb+k, k<b,因此,不论后续怎么博弈,一定可以出现a=k, b=b的情况。因此,无论这个局面是胜或负,先手者一定可以得到利于自己的局面。
若(k,b)为负,则先手者从a减去nb,则先手胜;若(k,b)为胜,先手者从a减去(n-1)*b,则先手仍然胜。

当b<a<2*b时,只能对a减去b,然后进入下一轮仍旧按照上述策略博弈。

 /* 1525 */
#include <cstdio>
#include <cstring>
#include <cstdlib> void swap(int &a, int &b) {
int tmp = a;
a = b;
b = tmp;
} int main() {
int a, b;
bool flag; #ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif while (scanf("%d%d",&a,&b)!=EOF && (a||b)) {
if (a < b)
swap(a, b);
flag = true;
while () {
if (a==b || a>=*b)
break;
a -= b;
if (a < b)
swap(a, b);
flag = !flag;
}
if (flag)
puts("Stan wins");
else
puts("Ollie wins");
} return ;
}
上一篇:pb数据窗口设置操作


下一篇:WCF之服务元数据