CSES 3214 - Water Containers Queries

1.0s 512M

有兩個水容器：容器 \(A\) 的容量是 \(a\)，容器 \(B\) 的容量是 \(b\)。你想要用這兩個容器量出 \(x\) 單位的水。

一開始兩個容器都是空的。每個操作可以把一個容器裝滿、把一個容器倒空，或是把水從一個容器倒進另一個容器。倒水的時候，必須倒到至少有一個容器被裝滿或被倒空。所有操作結束後，容器 \(A\) 裡必須有 \(x\) 單位的水。

你的任務是有效率地判斷在數組情形下，能不能量出這些水。

第一行有一個整數 \(n\)：測試的筆數。

接下來有 \(n\) 行，每行有三個整數 \(a\)、\(b\) 和 \(x\)。

對每一筆測試，若能量出這些水就輸出 YES，否則輸出 NO。

7
5 3 4
1 1 1
1 1 2
2 2 1
123 456 42
1000 999 123
1000 998 123

YES
YES
NO
NO
YES
YES
NO

題目來自 CSES Problem Set（Antti Laaksonen），授權 CC BY-NC-SA 4.0；本頁為翻譯，以相同授權分享。

題目頁說明