Hiểu bài toán

Xác định xem có thể dùng hai chiếc bình dung tích a và b để lấy được chính xác c lít nước hay không. Chúng ta chỉ có thể thực hiện các thao tác rót nước vào bình, đổ nước đi hoặc đổ nước từ bình này sang bình kia cho đến khi đầy hoặc hết. Đây là bài toán tìm nghiệm nguyên không âm (x, y) sao cho a*x + b*y = c hoặc a*x - b*y = c (và ngược lại) trong điều kiện lượng nước trong bình không vượt quá dung tích.

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

Cách BFS (Duyệt theo trạng thái)

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

int a, b, c;
bool visited[1005][1005];

void solve() {
    cin >> a >> b >> c;
    memset(visited, 0, sizeof(visited));
    queue<pair<int, int>> q;
    q.push({0, 0});
    visited[0][0] = true;
    bool found = false;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if (x == c || y == c) {
            found = true;
            break;
        }
        // 1. Rót đầy bình a
        if (!visited[a][y]) { visited[a][y] = true; q.push({a, y}); }
        // 2. Rót đầy bình b
        if (!visited[x][b]) { visited[x][b] = true; q.push({x, b}); }
        // 3. Đổ hết bình a
        if (!visited[0][y]) { visited[0][y] = true; q.push({0, y}); }
        // 4. Đổ hết bình b
        if (!visited[x][0]) { visited[x][0] = true; q.push({x, 0}); }
        // 5. Đổ a sang b
        int pour = min(x, b - y);
        if (!visited[x - pour][y + pour]) { visited[x - pour][y + pour] = true; q.push({x - pour, y + pour}); }
        // 6. Đổ b sang a
        pour = min(y, a - x);
        if (!visited[x + pour][y - pour]) { visited[x + pour][y - pour] = true; q.push({x + pour, y - pour}); }
    }
    cout << (found ? "YES" : "NO") << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

• Time Complexity: O(a * b)
• Space Complexity: O(a * b)

Cách tiếp cận này mô phỏng trực tiếp các thao tác với bình nước. Sử dụng BFS (tìm kiếm theo chiều rộng) để duyệt qua tất cả các trạng thái có thể có của hai bình nước (số nước trong bình a và b). Mỗi trạng thái là một cặp (x, y) với 0 <= x <= a, 0 <= y <= b. Khi một trạng thái có x == c hoặc y == c, ta tìm thấy đáp án. Vì a, b <= 1000, số lượng trạng thái tối đa là khoảng 1 triệu, phù hợp với thời gian chạy của C++ trong giới hạn 100 test case (tuy nhiên nếu a và b lớn, phương pháp này sẽ chậm).

Cách Số học (Thuyết Bézout)

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

void solve() {
    int a, b, c;
    cin >> a >> b >> c;
    int g = __gcd(a, b);
    // Điều kiện 1: c phải chia hết cho ước chung lớn nhất của a và b
    // Điều kiện 2: c không được lớn hơn dung tích lớn nhất của 2 bình
    if (c % g == 0 && c <= max(a, b)) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

• Time Complexity: O(log(min(a, b)))
• Space Complexity: O(1)

Đây là phương pháp tối ưu nhất dựa trên lý thuyết số. Theo định lý Bézout, một phương trình tuyến tính ax + by = c có nghiệm nguyên nếu và chỉ nếu c chia hết cho gcd(a, b). Tuy nhiên, trong bài toán bình nước, chúng ta chỉ có thể lấy được lượng nước c nếu c nhỏ hơn hoặc bằng dung tích của bình lớn nhất (vì lượng nước trong một bình không thể vượt quá dung tích của nó). Do đó, ta chỉ cần kiểm tra hai điều kiện: c % gcd(a, b) == 0 và c <= max(a, b).

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

Bài học kinh nghiệm

• Vấn đề có thể được quy về bài toán tìm nghiệm nguyên không âm của phương trình tuyến tính ax + by = c.
• Theo định lý Bézout, c có thể được tạo ra từ a và b nếu và chỉ nếu c chia hết cho gcd(a, b).
• Ngoài ra, cần đảm bảo c không vượt quá dung tích lớn nhất của hai bình do giới hạn vật lý.

Lỗi thường gặp

• Quên kiểm tra điều kiện c <= max(a, b). Ví dụ với a=2, b=4, c=6, gcd=2 chia hết 6 nhưng ta không thể lấy được 6 lít nước (vì bình lớn nhất chỉ chứa được 4 lít).
• Sử dụng thuật toán duyệt (BFS/DFS) cho các giá trị a, b lớn (ví dụ 10^5) sẽ gây TLE (Time Limit Exceeded) do độ phức tạp không cho phép.