ปัญหาน้ำและถังใน C++

มีถังสองใบ ความจุ x และ y ลิตร น้ำไม่จำกัด ต้องการทราบว่า วัดน้ำได้ z ลิตรพอดีหรือไม่ (น้ำอาจอยู่ในถังใดถังหนึ่งหรือทั้งสอง) 操作ที่อนุญาต: เติมน้ำเต็มถัง, เทน้ำทิ้ง, เทน้ำระหว่างถังจนเต็มหรือว่าง

ตัวอย่าง: x=3, y=5, z=4 → true

ขั้นตอนการแก้ปัญหา (Bézout's Identity / GCD)

1. ถ้า x + y < z → false (น้ำรวมไม่พอ)
2. ถ้า x == z || y == z || x + y == z → true
3. มิฉะนั้น: ตรวจสอบ z % gcd(x, y) == 0

ทฤษฎี: ด้วยการเทน้ำระหว่างถัง สามารถสร้างปริมาณน้ำได้ทุกค่าที่เป็นพหุคูณของ gcd(x,y) และไม่เกิน x+y

ตัวอย่างโค้ด 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);
}

Input

3 5 4

Output

1