题解 | #取石子#

#include <bits/stdc++.h>
using namespace std;

// 记忆化数组，-1 表示未计算，0 表示必胜态，1 表示必败态
int memo[101][101];

int solve(int n1, int n2) {
    // 如果状态已计算，直接返回
    if (memo[n1][n2] != -1) return memo[n1][n2];
    
    // 可能的取石子数
    int moves[] = {1, 3, 9};
    
    // 尝试所有合法操作
    for (int k : moves) {
        // 从第一堆取 k 个石子
        if (n1 >= k) {
            if (solve(n1 - k, n2) == 1) { // 后继状态是必败态
                return memo[n1][n2] = 0; // 当前状态是必胜态
            }
        }
        // 从第二堆取 k 个石子
        if (n2 >= k) {
            if (solve(n1, n2 - k) == 1) { // 后继状态是必败态
                return memo[n1][n2] = 0; // 当前状态是必胜态
            }
        }
    }
    
    // 如果所有后继状态都是必胜态，当前状态是必败态
    return memo[n1][n2] = 1;
}

int main() {
    // 初始化记忆化数组
    memset(memo, -1, sizeof(memo));
    // 特殊情况：(0,0) 是必败态，因为无法操作
    memo[0][0] = 1;
    
    int n1, n2;
    while (cin >> n1 >> n2) {
        // 判断状态 (n1, n2) 是否为必胜态
        if (solve(n1, n2) == 0) {
            cout << "win\n";
        } else {
            cout << "lose\n";
        }
    }
    
    return 0;
}