Hiểu bài toán

Bài toán Tháp xu (Tháp xu_) là một trò chơi hai người chơi trên một chồng xu. Người chơi A đi trước và hai người thay nhau lấy xu. Mỗi lần đến lượt, người chơi có thể lấy 1, K hoặc L xu khỏi chồng. Người chơi nào không thể lấy xu (khi chồng đã hết xu) sẽ thua. Cho các giá trị N (số xu ban đầu) cho nhiều trò chơi khác nhau, hãy xác định người thắng cuộc (A nếu người đi trước thắng, B nếu người đi trước thua) với K, L cố định.

Đây là bài toán trò chơi trò chơi (Game Theory) cơ bản, c cụ thể là một trò chơi impartial (hai người chơi có các nước đi giống nhau). Trạng thái thua-lợi nhuận (Win/Lose) của một trạng thái có thể suy ra từ các trạng thái trước đó. Một trạng thái là Losing (Thua) nếu tất cả các nước đi hợp lệ đều dẫn đến trạng thái Winning (Thắng) của đối thủ. Một trạng thái là Winning (Thắng) nếu có ít nhất một nước đi dẫn đến trạng thái Losing (Thua) của đối thủ.

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

Cách Quy hoạch động (Dynamic Programming)

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

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

    int K, L, m;
    cin >> K >> L >> m;

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

    vector<bool> win(maxN + 1, false);
    win[0] = false; // Ko có xu -> Thua

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

    for (int x : N) {
        cout << (win[x] ? 'A' : 'B');
    }

    return 0;
}

• Time Complexity: O(max(N))
• Space Complexity: O(max(N))

Đây là cách tiếp cận trực tiếp và phổ biến nhất trong các bài nộp.

1. Mảng win: Dùng mảng boolean win[i] để lưu kết quả cho số xu i. true nghĩa là người chơi hiện tại (người đi trước) thắng nếu bắt đầu với i xu.
2. Cơ sở: win[0] = false. Nếu không còn xu, bạn không thể đi nước nào và thua ngay lập tức.
3. Công thức truy hồi: Với mỗi i từ 1 đến maxN, ta kiểm tra các nước đi có thể:
   • Lấy 1 xu: đến trạng thái i-1.
   • Lấy K xu (nếu i >= K): đến trạng thái i-K.
   • Lấy L xu (nếu i >= L): đến trạng thái i-L. Nếu có bất kỳ trạng thái nào trong số này là false (thua) thì người hiện tại có thể đi nước đó để ép đối thủ vào thế thua, do đó win[i] = true. Nếu tất cả đều là true (đối thủ thắng), thì win[i] = false.
4. Độ phức tạp: Với maxN là giá trị lớn nhất trong các N, ta cần O(maxN) thời gian và bộ nhớ. Trong các bài nộp, maxN có thể lên tới 10^6 hoặc 10^7, nên ta cần khai báo mảng lớn (ví dụ const int MAXN = 1e7 + 5; hoặc dùng vector nếu maxN đọc vào nhỏ).

Cách Tối ưu quy luật toán học (Nếu K, L có ước chung)

// Pseudocode minh họa logic
// Chỉ hoạt động hiệu quả nếu GCD(K, L) = 1 để tạo ra chu kỳ đủ dài
// Hoặc dùng cho nhận dạng quy luật nhanh

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

bool isWin(int n, int k, int l) {
    int g = gcd(k, l);
    // Nếu n không chia hết cho GCD, có thể có nước đi đặc biệt
    // Tuy nhiên, logic chính xác vẫn là DP cho đến khi tìm được quy luật Periodic
    // Ví dụ: Nếu K=2, L=3, quy luật là L, W, L, W... (Thừa số chung)
    // Nếu K=2, L=4, quy luật phụ thuộc vào số chẵn/lẻ.
    // Do tính chất 'Impartial', trò chơi này có tính Periodic (chu kỳ).
    // Sau một đoạn đầu, kết quả sẽ lặp lại với chu kỳ là (K + L).
    // Tuy nhiên, để an toàn và chung chung, DP là cách tốt nhất.
    return false; 
}

• Time Complexity: O(1) sau khi tính toán quy luật
• Space Complexity: O(1)

Đây là cách tiếp cận mang tính học thuật.

1. Tính chất Periodic: Các trò chơi trò chơi impartial trên dãy số (như Nim biến thể) thường có tính chu kỳ (Periodicity). Nghĩa là sau một đoạn đầu P, kết quả win[i] sẽ lặp lại với chu kỳ T.
2. Phân tích: Nếu gcd(K, L) = 1, trò chơi thường có chu kỳ K + L hoặc K * L. Nếu gcd(K, L) > 1, trò chơi có thể chia làm các lớp theo số dư modulo của GCD.
3. Khi nào dùng: Cách này hữu ích khi maxN quá lớn (ví dụ 10^12) không thể DP mảng. Tuy nhiên, việc chứng minh và tìm chính xác chu kỳ cho mọi K, L là phức tạp. Trong các bài thi thực tế, DP mảng là đủ và an toàn.

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

Bài học kinh nghiệm

• Bài toán là trò chơi hai người chuẩn tắc (Impartial Game), có thể giải bằng Dynamic Programming.
• Trạng thái 'Thua' (Losing) chỉ xảy ra khi tất cả các nước đi hợp lệ đều dẫn đến Trạng thái 'Thắng' (Winning) của đối thủ.
• Vì có nhiều test case (m) nhưng K, L cố định, ta chỉ cần tính mảng DP một lần duy nhất cho max(N) và tra câu trả lời cho các N còn lại.

Lỗi thường gặp

• Quên kiểm tra điều kiện i >= K và i >= L trước khi truy cập mảng, dẫn đến lỗi truy cập ngoài vùng nhớ (nếu dùng mảng tĩnh và truy cập âm) hoặc lỗi logic.
• Sử dụng kiểu int cho mảng win thay vì bool có thể gây tốn bộ nhớ hơn cần thiết (4 bytes so với 1 byte), nhưng vẫn đúng logic.
• Lỗi nhập xuất: Quên ios::sync_with_stdio(false); cin.tie(nullptr); có thể gây trễ nếu maxN lớn và in nhiều ký tự.