【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 ;

 }

巴特西

【HDOJ】1525 Euclid's Game

最新文章

热门文章