《算法竞赛·快冲300题》每日一题：“取石子游戏”

《算法竞赛·快冲300题》将于2024年出版，是《算法竞赛》的辅助练习册。
所有题目放在自建的OJ New Online Judge。
用C/C++、Java、Python三种语言给出代码，以中低档题为主，适合入门、进阶。

“ 取石子游戏” ，链接： http://oj.ecustacm.cn/problem.php?id=1119

题目描述

【题目描述】 有两堆石子，两个人轮流去取。每次取的时候，只能从较多的那堆石子里取，并且取的数目必须是较少的那堆石子数目的整数倍，最后谁能够把一堆石子取空谁就算赢。给定初始时石子的数目，如果两个人都采取最优策略，请问先手能否获胜。
【输入格式】 输入包含多数数据。每组数据一行，包含两个正整数a和b，表示初始时石子的数目。a, b≤109。输入以两个0表示结束。
【输出格式】 如果先手胜，输出"win"，否则输出"lose"。
【输入样例】

34 12
15 24
0 0
1
2
3

【输出样例】

win
lose
1
2

---

题解

   设a≥b。当前能取空石子的获胜，那么要求当前的局面是a=kb，即a是b的整数倍，取空a后获胜。
   第一个样例“34, 12”的取法是：
      甲：34-24, 12 -> 10, 12
      乙：10, 12-10 -> 10, 2， 乙只有这一种取法
      甲：10-10, 2 -> 0, 2， 甲胜
   读者可以自行模拟第二个样例。
   下面讨论不同情况下的游戏局面。设开始时a≥b。
   （1）局面1：a = b。先手胜，因为他能取空一堆。
   （2）局面2：b < a < 2b。此局面对先手不利，因为他没有选择，只能在a这一堆中取b，剩下a-b。新的两堆是a’ = b，b’ = a-b。注意有a’≠b’，游戏并没有结束，先手还有机会。如果下一步仍有b’    （3）局面3：a≥2b。
   如果a刚好是b的整k倍，a = kb，那么先手直接取空a=kb，先手胜。
   如果a不是b的整倍，先手可以取b的某个倍数，转为局面2的情况，让对方不利，并且让后续局面轮到自己时仍保持优势。
   例如a=13，b=5，甲先手，这样取：
      甲：13-5, 5 -> 8, 5， 下一步的(8, 5)转为局面2，让乙处于不利局面
      乙：8-5, 5 -> 3, 5， 乙只有这一种选择
      甲：3, 5-3 -> 3, 2， 甲也只有这一种选择
      乙：3-2, 2 -> 1, 2， 乙只有这一种选择
      甲：1, 2-2 -> 1, 0， 甲胜
   如果甲的第一步没取对，会导致失败：
      甲：13-10, 5 -> 3, 5
      乙：3, 5-3 -> 3, 2， 乙只有这一种选择
      甲：3-2, 2 -> 1, 2， 甲也只有这一种选择
      乙：1, 2-2 -> 1, 0， 乙胜
   也就是说，甲有两种选择，一种失败，一种赢，他肯定选赢的那种。
   总结以上讨论，先手获胜的条件是当前处于局面1和局面3。
【重点】 局面分析 。

C++代码

   在dfs()中转换游戏局面并返回结果。dfs()的复杂度是多少？第6行当b < a < 2b时执行dfs(a-b, b)，每次a-b至少减一半，所以复杂度是$O(loga)$的，当$a=10^9$时，$loga=30$。

#include
using namespace std;
bool dfs(int a, int b){
    if(a < b)  swap(a, b);      //保证多的石子在前
    if(a >= 2*b || a==b) return true;  //当前处于局面1、局面3，获胜
    return !dfs(a-b, b);      //局面2，对方只能取a-b
}
int main(){
    int a, b;
    while(cin>>a>>b && (a+b)) {
        if(dfs(a, b)) cout<<"win" <<endl;
        else          cout<<"lose"<<endl;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Java代码

import java.util.Scanner;
public class Main {
    public static boolean dfs(int a, int b) {
        if (a < b) {
            int temp = a;
            a = b;
            b = temp;
        }
        if (a >= 2 * b || a==b)  return true;
        return !dfs(a - b, b);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            if (a == 0 && b == 0)  break;            
            if (dfs(a, b)) System.out.println("win");
            else           System.out.println("lose");            
        }
        sc.close();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Python代码

def dfs(a, b):
    if a < b:  a, b = b, a           #交换
    if a >= 2 * b or a==b: return True
    return not dfs(a - b, b) 
while True:
    a, b = map(int, input().split())
    if a == 0 and b == 0:  break
    if dfs(a, b):  print("win")
    else:          print("lose")
1
2
3
4
5
6
7
8
9