Lời giải

Phân tích

Bài toán là một trò chơi tổ hợp (impartial combinatorial game). Với mỗi kích thước đống đá \(x\), ta xác định:

• Nếu \(x = 1\) hoặc \(x = 2\): không thể chia thành hai phần khác nhau → thua.
• Nếu \(x \ge 3\): có thể chia thành \((1, x-1)\), \((2, x-2)\), ..., miễn là hai phần khác nhau.

Gọi \(win[x] = true\) nếu người đi trước thắng với đống \(x\). Công thức:

• \(win[x] = true\) nếu tồn tại cách chia \(x = a + b\) (\(a \neq b\), \(a, b > 0\)) sao cho \(win[a] = false\) hoặc \(win[b] = false\) (chọn phần làm đối thủ thua).
• Ngược lại, \(win[x] = false\).

Độ phức tạp: \(O(N^2)\) với \(N \le 1000\) là chấp nhận được.

Mã nguồn C++

// Giải thuật ab cho bài toán ab-stone-div\n#include <bits/stdc++.h>
using namespace std;

int main() {
    // Doc du lieu dau vao
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<bool> win(n + 1, false);
    for (int x = 3; x <= n; x++) {
        win[x] = false;
        for (int a = 1; a < x; a++) {
            int b = x - a;
            if (a == b) continue;
            if (!win[a] || !win[b]) {
                win[x] = true;
                break;
            }
        }
    }
    cout << (win[n] ? 1 : 2) << "\n";
    return 0;
}