ปัญหาน้ำและเหยือกใน C++

สมมติว่าเรามีเหยือกสองใบที่มีความจุ x และ y ลิตร มีน้ำประปาให้เราใช้ได้อย่างไม่จำกัด ตอนนี้ เราต้องพิจารณาว่าสามารถวัด z ลิตรได้อย่างแม่นยำโดยใช้เหยือกทั้งสองนี้หรือไม่ หากวัดปริมาณน้ำได้ z ลิตร เราจะต้องมีน้ำ z ลิตรอยู่ภายในถังเดียวหรือทั้งสองถังในตอนท้าย

เราสามารถดำเนินการบางอย่างเหล่านี้ได้ -

• เติมน้ำในเหยือกให้เต็ม

• ล้างเหยือกใดก็ได้

• เทน้ำจากเหยือกหนึ่งไปยังอีกเหยือกหนึ่งจนเหยือกอื่นเต็มหรือเหยือกแรกว่างเปล่า

ดังนั้นหาก x =2 และ y =5 และ z =4 ค่านั้นจะกลับมาเป็นจริง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ถ้า x + y

• ถ้า x =z หรือ y =z หรือ x + y =z ให้คืนค่า true

• คืนค่า true z หารด้วย gcd ของ x และ y หารลงตัว ไม่เช่นนั้น false

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h&g;
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 % __gcd(x, y) == 0;
   }
};
main(){
   Solution ob;
   cout << (ob.canMeasureWater(3,5,4));
}

อินพุต

3
5
4

ผลลัพธ์

1