27623: 取石子-较少那堆石子数目的整数倍

http://cs101.openjudge.cn/practice/27623/

有两堆石子,两个人轮流去取。每次取的时候,只能从较多的那堆石子里取,并且取的数目必须是较少的那堆石子数目的整数倍，最后谁能够把一堆石子取空谁就算赢。

比如初始的时候两堆石子的数目是25和7。 25 7 --> 11 7 --> 4 7 --> 4 3 --> 1 3 --> 1 0 选手1取选手2取选手1取选手2取选手1取最后选手1（先取的）获胜，在取的过程中选手2都只有唯一的一种取法。给定初始时石子的数目，如果两个人都采取最优策略，请问先手能否获胜。

输入

输入包含多数数据。每组数据一行，包含两个正整数a和b，表示初始时石子的数目。( a,b <= 10^9 ) 输入以两个0表示结束。

输出

如果先手胜，输出"win"，否则输出"lose"。

样例输入

34 12 
15 24 
0 0

样例输出

win 
lose

提示

假设石子数目为(a,b)且a >= b,如果[a/b] >= 2则先手必胜,如果[a/b]<2,那么先手只有唯一的一种取法。[a/b]表示a除以b取整后的值。

来源：https://zhuanlan.zhihu.com/p/435100856

题目描述的这个问题是一个经典的博弈论问题，可以根据给定的规则来决定先手是否必胜。下面是对这个问题的一个简单分析和一个基于分析的简单代码实现。分析：

对于任何一个状态 $ (data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABCAYAAAAfFcSJAAAAAXNSR0IArs4c6QAAAAtJREFUGFdjYAACAAAFAAGq1chRAAAAAElFTkSuQmCC)$ (a,b)，其中 a >=b：

如果 a 是 b 的整数倍，那么先手可以直接取完 a，因此先手必胜。
如果 a 是 b 的整数倍加上一个余数 r，即 $a = k * b + r$ ，其中 k >=2，则先手可以取走 k - 1 倍的 b，使得对方面对的是 $(b + r, b)$ ，这是一个对称状态，因此先手必胜。对称状态意味着接下来无论对手如何操作，先手都可以复制对手的操作，直到最后取走所有石子。
如果 a < 2∗b，即 a 无法一次性取到 2 倍以上的 b，则游戏会继续进行。在这种情况下，先手的目标是通过取走一定数量的石子，使得剩下的数量变为(new_a, new_b)其中 new_a < 2∗new_b，这样就转移到了后手。如果后手也面临同样的情况，则他会做出同样的操作，游戏将继续这样进行，直到某一方无法继续这样的操作，即 a/b>=2的时候，那一方就会输。

每一步相除所得的商都大于1，即对于每一局的初状态（a，b），a > b，都满足：a/b > 1。对这种情况，我们的策略是取走（a/b－1）*b，这样就得到新状态（a mod b + b，b），接下来，对手就没有选择，只能取走b，剩下（a mod b，b），而这就是下一局的初状态，这样就保证下一局的初状态肯定由自己取，这种情况下先取者必胜。

python

def dfs(a, b):
    # 优先达到条件者获胜
    if a // b >= 2 or a == b:
        return True
    else:
        # 继续回溯，如果后手先遇到，则后手胜利
        return not dfs(b, a - b)

while True:
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        break
    
    # 保证多的石子在前
    if b > a:
        a, b = b, a
    
    # 调用回溯，直到遇到第一次 a/b >= 2
    if dfs(a, b):
        print("win")
    else:
        print("lose")

cpp

#include<bits/stdc++.h> 
using namespace std; 
bool Dfs(int a, int b) { 
    //优先达到条件者获胜 
    if (a / b >= 2 || a == b) { 
       return true; 
     } else { 
     //继续回溯，如果后手先遇到，则后手胜利 
     return !Dfs(b, a - b); 
     } 
} 
int main() { 
    //定义输入的a，b两堆石子 
    int a, b; 
    //持续获得输入 
    while ((cin >> a >> b) && !(a == 0 && b == 0)) { 
     //保证多的石子在前 
    if (b > a) { 
       swap(a, b); 
    } 
    //调用回溯，直到遇到第一次a/b>=2 
    if (Dfs(a, b)) 
       cout << "win" << endl; 
    else 
       cout << "lose" << endl; 
    } 
    return 0; 
}

27623: 取石子-较少那堆石子数目的整数倍 ​

27623: 取石子-较少那堆石子数目的整数倍