Hiểu bài toán

Hai người chơi Tú và Tuấn tung xúc xắc để về đích. Người nào tung ít lần hơn sẽ thắng. Nếu tung cùng số lần thì hòa. Quy tắc đặc biệt: nếu tổng điểm vượt quá đích, người chơi sẽ lùi lại (trừ đi số điểm đích) cho đến khi chạm đích. Số điểm tối đa của xúc xắc cho Tú là n, của Tuấn là m (1 ≤ n, m ≤ 6). Cần tìm số lượt tung tối thiểu để đạt đúng điểm d (10 ≤ d ≤ 10000).

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

Cách Mô phỏng quy trình (Simulation)

#include <iostream>
using namespace std;

int step(int a, int x) {
    int current = 0, cnt = 0;
    while (current != a) {
        if (current > a) {
            current -= a;
        } else {
            current += x;
            cnt++;
        }
    }
    return cnt;
}

int main() {
    int n, m, d;
    cin >> n >> m >> d;
    int tu = step(d, n);
    int tuan = step(d, m);
    if (tu < tuan) cout << 1;
    else if (tuan < tu) cout << -1;
    else cout << 0;
    return 0;
}

• Time Complexity: O(d) - phụ thuộc vào số bước mô phỏng
• Space Complexity: O(1)

Giải pháp này mô phỏng chính xác quá trình chơi. Hàm step bắt đầu từ 0, lặp lại việc tung xúc xắc (cộng điểm) cho đến khi vượt quá đích, sau đó trừ đi d cho đến khi bằng đúng d. Biến cnt đếm số lần tung. Do d tối đa là 10000 và bước nhảy nhỏ, độ phức tạp chấp nhận được.

Cách Tối ưu bằng số học (GCD)

#include <iostream>
#include <numeric>
using namespace std;

int main() {
    int n, m, d;
    cin >> n >> m >> d;
    int t1 = d / gcd(n, d);
    int t2 = d / gcd(m, d);
    if (t1 < t2) cout << 1;
    else if (t1 > t2) cout << -1;
    else cout << 0;
    return 0;
}

• Time Complexity: O(log(min(n, d))) - thời gian tính GCD
• Space Complexity: O(1)

Bài toán có thể quy về bài toán tìm số bước nhỏ nhất để tạo ra tổng bội của d bằng các số n hoặc m. Số bước tối thiểu để đạt được điểm d (theo quy tắc trừ lùi) tương đương với số bội của gcd(n, d) cần thiết để tạo thành d. Cụ thể, số bước là d / gcd(n, d). Cách này loại bỏ vòng lặp mô phỏng và chạy siêu nhanh.

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solve_dp(int d, int x) {
    vector<int> dp(d + 1, 1e9);
    dp[0] = 0;
    for (int i = 1; i <= d; i++) {
        for (int j = 1; j <= x; j++) {
            int prev = i - j;
            if (prev < 0) prev += d; // Quy tắc lùi lại
            dp[i] = min(dp[i], dp[prev] + 1);
        }
    }
    return dp[d];
}

int main() {
    int n, m, d;
    cin >> n >> m >> d;
    int tu = solve_dp(d, n);
    int tuan = solve_dp(d, m);
    if (tu < tuan) cout << 1;
    else if (tuan < tu) cout << -1;
    else cout << 0;
    return 0;
}

• Time Complexity: O(d * 6) - do n, m <= 6
• Space Complexity: O(d)

Xây dựng mảng DP dp[i] là số bước ít nhất để đạt điểm i. Từ mỗi trạng thái i, ta thử tất cả các bước nhảy j (từ 1 đến x). Nếu i + j vượt quá d, ta dùng quy tắc lùi lại. Đây là cách tiếp cận tổng quát nhưng phức tạp hơn phương pháp GCD.

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

Bài học kinh nghiệm

• Vấn đề có tính chất lặp lại (đặc biệt khi vượt đích), có thể tối ưu bằng toán học thay vì mô phỏng.
• Số bước tối thiểu để đạt điểm d tương đương với số lượng số n (hoặc m) cần thiết để tạo thành bội của d, quy ra công thức d / gcd(n, d).

Lỗi thường gặp

• Quên xử lý trường hợp tổng điểm vượt quá đích (phép trừ lùi).
• Sử dụng thuật toán tìm đường đi thông thường (BFS/DFS) có thể gây tràn bộ nhớ hoặc quá thời gian nếu không giới hạn trạng thái đúng cách.