Hiểu bài toán

Trò chơi này là một biến thể của trò chơi Nim. Có N đồng xu trên một đống. Hai người chơi Alice và Bob thay phiên nhau bốc xu. Alice đi trước. Mỗi người có thể bốc 1, K hoặc L xu (K và L là hai số nguyên dương khác nhau). Nếu số xu còn lại ít hơn K hoặc L, người chơi chỉ được bốc 1 xu. Người chơi bốc được đồng xu cuối cùng sẽ thắng. Nhiệm vụ là xác định người thắng cuộc nếu cả hai chơi tối ưu.

Đây là một trò chơi tổng số (sum game) và có thể được giải quyết bằng phương pháp quy hoạch động (Dynamic Programming) để tính toán trạng thái thắng/thua cho mỗi số lượng xu từ 0 đến N. Trạng thái 'Thắng' (Winning state) là trạng thái mà người chơi hiện tại có thể di chuyển đến một trạng thái 'Thua' (Losing state) của đối thủ. Trạng thái 'Thua' là trạng thái mà tất cả các nước đi hợp lệ đều dẫn đến trạng thái 'Thắng' của đối thủ.

• Trạng thái 0 (0 xu): Thua (người chơi không thể đi nước nào).
• Trạng thái i (i xu): Thắng nếu tồn tại một nước đi (bốc 1, K hoặc L xu) đến trạng thái i-1, i-K hoặc i-L là trạng thái Thua. Ngược lại, là Thua.

Các cách tiếp cận

Cách Quy hoạch động cơ bản (DP)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T, K, L;
    cin >> T >> K >> L;

    vector<int> N(T);
    int maxN = 0;
    for (int i = 0; i < T; i++) {
        cin >> N[i];
        maxN = max(maxN, N[i]);
    }

    vector<bool> dp(maxN + 1, false);
    dp[0] = false; // Không còn xu -> thua
    for (int i = 1; i <= maxN; i++) {
        if (i >= 1 && !dp[i - 1]) dp[i] = true;
        else if (i >= K && !dp[i - K]) dp[i] = true;
        else if (i >= L && !dp[i - L]) dp[i] = true;
        else dp[i] = false;
    }

    for (int i = 0; i < T; i++) {
        cout << (dp[N[i]] ? 'A' : 'B');
    }
    cout << '\n';

    return 0;
}

• Time Complexity: O(T + N_max)
• Space Complexity: O(N_max)

Đây là phương pháp trực tiếp nhất để giải quyết bài toán quy hoạch động. Chúng ta tạo một mảng dp với dp[i] là true nếu người chơi có thể thắng khi bắt đầu với i xu, và false nếu người chơi thua.

1. Khởi tạo: dp[0] = false (vì không thể đi nước nào, người chơi thua).
2. Quy hoạch: Duyệt i từ 1 đến N_max (số xu lớn nhất trong các test case).
   • Kiểm tra các nước đi hợp lệ: bốc 1, K, hoặc L xu.
   • Nếu có ít nhất một nước đi dẫn đến trạng thái thua cho đối thủ (tức là dp[i - move] == false), thì dp[i] = true.
   • Nếu tất cả các nước đi đều dẫn đến trạng thái thắng cho đối thủ, thì dp[i] = false.
3. Trả lời: Duyệt qua các giá trị N đầu vào và in ra 'A' nếu dp[N] == true, ngược lại in 'B'.

Độ phức tạp:

• Thời gian: O(Nmax) để tính toán mảng DP và O(T) để trả lời các truy vấn. Tổng cộng là O(T + Nmax). Với N_max lên tới 10^6, phương pháp này rất nhanh.
• Bộ nhớ: O(N_max) để lưu mảng DP.

Cách Xử lý nhiều test case (Tối ưu)

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

int main() {
    int T, K, L;
    cin >> T >> K >> L;

    vector<int> tests(T);
    int max_N = 0;
    for (int i = 0; i < T; ++i) {
        cin >> tests[i];
        max_N = max(max_N, tests[i]);
    }

    vector<bool> dp(max_N + 1, false);
    dp[0] = false;

    for (int i = 1; i <= max_N; ++i) {
        bool win = false;
        if (i >= 1 && !dp[i - 1]) win = true;
        if (i >= K && !dp[i - K]) win = true;
        if (i >= L && !dp[i - L]) win = true;
        dp[i] = win;
    }

    string result;
    for (int n : tests) {
        result += (dp[n] ? "A" : "B");
    }

    cout << result << endl;

    return 0;
}

• Time Complexity: O(T + N_max)
• Space Complexity: O(N_max)

Đây là phiên bản slightly cleaner của phương pháp DP cơ bản. Thay vì chỉ gán giá trị boolean trực tiếp, chúng ta tính toán trạng thái winning trước rồi gán vào mảng. Logic hoàn toàn giống với Approach 1.

Phương pháp này nhấn mạnh vào việc xử lý đầu vào nhiều test case một cách hiệu quả bằng cách:

1. Đọc tất cả các giá trị N và tìm giá trị lớn nhất (max_N).
2. Chỉ cần chạy một vòng lặp quy hoạch động duy nhất lên đến max_N.
3. Lưu kết quả vào một chuỗi ký tự để in ra một lần.

Điều này đảm bảo rằng chúng ta không cần phải chạy lại thuật toán cho mỗi test case riêng lẻ, giảm đáng kể thời gian thực thi khi T lớn.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán này là một trò chơi 'tổng số' (impartial game), có thể giải bằng quy hoạch động trạng thái thắng/thua (Winning/Losing positions).
• Trạng thái 'Thua' (Losing) là trạng thái mà mọi nước đi hợp lệ đều dẫn đến trạng thái 'Thắng' của đối thủ.
• Trạng thái 'Thắng' (Winning) là trạng thái mà người chơi có ít nhất một nước đi đến trạng thái 'Thua' của đối thủ.
• Nếu N < K và N < L, người chơi chỉ được bốc 1 xu. Khi đó, kết quả phụ thuộc vào tính chẵn lẻ của N (N chẵn -> Bob thắng, N lẻ -> Alice thắng). Tuy nhiên, thuật toán DP tự động xử lý trường hợp này.

Lỗi thường gặp

• Sai lệch trong việc kiểm tra điều kiện bốc xu (ví dụ: kiểm tra i > K thay vì i >= K).
• Quên khởi tạo giá trị cơ sở dp[0] = false.
• Lỗi truy cập mảng ngoài biên (off-by-one error) khi i - K hoặc i - L nhỏ hơn 0.
• Xử lý nhiều test case không hiệu quả (tính toán lại DP cho mỗi test case).