Hướng dẫn giải của Trò chơi với những đồng xu

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, longnuub, trungkien1252010, thosanphuba

Hiểu bài toán

Trò chơi hai người (Alice và Bob) bắt đầu với một đống xu N. Lượt đi của Alice trước. Mỗi người có thể bốc 1, K hoặc L xu (với K và L là hai số nguyên dương khác nhau cho trước). Nếu số xu còn lại trong đống ít hơn K hoặc L, họ chỉ được bốc 1 xu. Người bốc được đồng xu cuối cùng sẽ thắng. Với T truy vấn (mỗi truy vấn cho trước số N), hãy xác định người thắng cuộc nếu cả hai chơi tối ưu.

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

Cách Quy hoạch động (Dynamic Programming)
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    int T;
    long long K, L;
    if (!(cin >> T >> K >> L)) return 0;
    vector<long long> tests(T);
    long long maxN = 0;
    for (int i = 0; i < T; ++i) {
        cin >> tests[i];
        if (tests[i] > maxN) maxN = tests[i];
    }

    vector<char> win(maxN + 1, 0);
    win[0] = 0;
    for (long long n = 1; n <= maxN; ++n) {
        bool w = false;
        // Chọn 1 xu
        if (!win[n-1]) w = true;
        // Chọn K xu
        if (!w && n >= K) {
            if (!win[n - K]) w = true;
        }
        // Chọn L xu
        if (!w && n >= L) {
            if (!win[n - L]) w = true;
        }
        win[n] = w ? 1 : 0;
    }

    string out;
    out.reserve(T);
    for (long long n : tests) {
        out += (win[n] ? 'A' : 'B');
    }
    cout << out << endl;
    return 0;
}
  • Time Complexity: O(T + maxN)
  • Space Complexity: O(maxN)

Đây là cách tiếp cận trực tiếp nhất. Ta định nghĩa win[n] là true nếu người chơi lượt hiện tại (người sắp đi) có thể thắng với đống xu size n. Công thức truy hồi: win[n] = !win[n-1] || (n >= K && !win[n-K]) || (n >= L && !win[n-L]). Ta tính mảng win từ 1 đến maxN (giá trị N lớn nhất trong các test case). Độ phức tạp thời gian là O(maxN) để tính toán và O(T) để in kết quả. Độ phức tạp không gian là O(maxN) để lưu mảng win. Với maxN lên tới 10^6, cách này chạy khá nhanh (vượt qua giới hạn thời gian trong các giải pháp đã cho).

Cách Quy hoạch động tối ưu không gian
#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    long long K, L;
    cin >> T >> K >> L;
    vector<long long> tests(T);
    long long maxN = 0;
    for (int i = 0; i < T; i++) {
        cin >> tests[i];
        maxN = max(maxN, tests[i]);
    }

    // Chỉ cần lưu trạng thái của các bước lùi tối đa max(K, L)
    // Tuy nhiên, để đơn giản và xử lý ngay lập tức, ta dùng mảng bool nhỏ
    // Nhưng do input yêu cầu xử lý nhiều test cùng K, L, ta nên tính trước.
    // Nếu maxN quá lớn (ví dụ 10^9), DP không dùng được. Nhưng bài này maxN=10^6.

    // Giả sử maxN vẫn là 10^6, ta dùng mảng bool 10^6 là được.
    // Code giải pháp 1 đã tối ưu về mặt này.

    // Code dưới đây là biến thể nếu ta muốn xử lý từng test case một cách độc lập
    // nhưng vẫn giữ logic DP.

    // Tuy nhiên, giải pháp gốc từ các submission đã dùng mảng bool cỡ maxN.
    // Ta sẽ giữ nguyên logic giải pháp 1 nhưng thêm chú thích về không gian.

    vector<char> win(maxN + 1, 0);
    win[0] = 0;
    for (long long n = 1; n <= maxN; ++n) {
        bool w = false;
        if (!win[n-1]) w = true;
        if (!w && n >= K && !win[n-K]) w = true;
        if (!w && n >= L && !win[n-L]) w = true;
        win[n] = w;
    }

    for (int i = 0; i < T; i++) {
        cout << (win[tests[i]] ? 'A' : 'B');
    }
    cout << endl;
    return 0;
}
  • Time Complexity: O(maxN)
  • Space Complexity: O(maxN)

Giải pháp này tương tự giải pháp 1 nhưng được trình bày lại để nhấn mạnh việc tính toán trước cho tất cả các test case. Vì K và L cố định cho tất cả các test, ta chỉ cần chạy DP một lần để điền vào mảng win. Sau đó, mỗi truy vấn chỉ mất O(1) để trả lời. Nếu maxN nhỏ (ví dụ 10^6), đây là cách hiệu quả nhất.

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

Cách tiếp cận Time Space Tên
1 O(T + maxN) O(maxN) Quy hoạch động (Dynamic Programming)
2 O(maxN) O(maxN) Quy hoạch động tối ưu không gian

Bài học kinh nghiệm

  • Bài toán này là một trò chơi hoàn hảo thông tin (perfect information game), có thể giải bằng Quy hoạch động (DP) cơ bản với trạng thái là số xu còn lại.
  • Giai đoạn cơ sở: Đống xu rỗng (n=0) là một trạng thái thua cuộc (losing state) đối với người chơi sắp đi.
  • Trạng thái n là thắng (winning) nếu tồn tại ít nhất một nước đi tới trạng thái thua cuộc của đối thủ.

Lỗi thường gặp

  • Truy cập ngoài mảng: Cần kiểm tra điều kiện n >= K và n >= L trước khi truy cập dp[n-K] và dp[n-L].
  • Hiểu sai điều kiện bốc xu: Bài toán cho phép bốc 1, K, hoặc L xu. Nếu số xu còn lại ít hơn K hoặc L, chỉ được bốc 1 xu. Logic DP if (n >= K ...) đã xử lý đúng điều này.

Bình luận

Please read the guidelines before commenting.

Không có bình luận tại thời điểm này.