首页 > 代码库 > 【HDOJ】1525 Euclid's Game
【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，然后进入下一轮仍旧按照上述策略博弈。
1 /* 1525 */ 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 6 void swap(int &a, int &b) { 7 int tmp = a; 8 a = b; 9 b = tmp;10 }11 12 int main() {13 int a, b;14 bool flag;15 16 #ifndef ONLINE_JUDGE17 freopen("data.in", "r", stdin);18 #endif19 20 while (scanf("%d%d",&a,&b)!=EOF && (a||b)) {21 if (a < b)22 swap(a, b);23 flag = true;24 while (1) {25 if (a==b || a>=2*b)26 break;27 a -= b;28 if (a < b)29 swap(a, b);30 flag = !flag;31 }32 if (flag)33 puts("Stan wins");34 else35 puts("Ollie wins");36 }37 38 return 0;39 }
【HDOJ】1525 Euclid's Game
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。