Vấn đề bình nước (Water and Jug Problem) trong C++

Mô tả bài toán

Hai bình dung tích x, y lít. Nguồn nước vô hạn. Các thao tác: đầy bình, đổ rỗng, đổ từ bình này sang bình kia cho đến khi đầy hoặc rỗng. Có thể đo được đúng z lít không?

Ví dụ: x=3, y=5, z=4 → true (đổ 5→3, còn 2 trong bình 5; đổ rỗng 3, chuyển 2 vào 3; đầy 5, đổ vào 3 (còn chỗ 1) → bình 5 còn 4).

Giải thuật Toán học (Bézout)

Có thể đo được z lít chỉ khi z là bội số của gcd(x, y) và z ≤ x + y.

• Nếu x + y < z → false.
• Nếu z == x || z == y || z == x+y → true.
• Ngược lại: z % gcd(x, y) == 0.

Cài đặt C++

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

class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        if (x + y < z) return false;
        if (x == z || y == z || x + y == z) return true;
        return z % std::gcd(x, y) == 0;
    }
};

int main() {
    Solution ob;
    cout << ob.canMeasureWater(3, 5, 4); // 1 (true)
    return 0;
}

Độ phức tạp

• Thời gian: O(log min(x,y)) (Euclid GCD).
• Không gian: O(1).