題目在 https://zerojudge.tw/ShowProblem?problemid=e527
這題舉例很詳細, 在其x=3, y=5, z=4的案例中,出現4公升的水 (0,4)。共需要8次，其步驟可以表示如下：(3, 0) – (0, 3) – (3, 3) –(1, 5) –(1, 0) –(0, 1) –(3, 1) –(0, 4)。 但是仔細看一下,其實只要七次就可以了. 第七次的3+1也是4公升只是裝在不同容器. 所以顯然正確答案是不容許裝在不同的容器一起算. 這樣就變簡單一些.
首先我們先判斷能不能做到. 簡單的說就是z如果是x,y的最大公因數的倍數,那就有解. 不過也不能比x,y都大. 因為不容許分成兩個容器裝.
cin >> x >> y >> z;
if(x<y) swap(x,y);
if (x==z || y==z){
cout << "1" << endl;
continue;
}
if (z>x || z % gcd(x, y) != 0) {
cout << "-1" << endl;
continue;
}因為兩個容器不同, 可能有大有小, 可以由大的往小的倒, 反過來也可以, 不知道到底哪個比較快, 所以就兩種都算一遍. 取快的答案就可以了. X2Y( )就是計算從X往Y倒水, Y2X( )計算從Y往X倒水, 因為寫法都一樣, 所以Y2X就不用再寫一遍, 把X2Y( )的x,y參數對調, 再用X2Y( )算一遍就可以.
int step1=X2Y(x, y, z);
//cout << "X2Y="<<step1<<endl;
int step2=X2Y(y, x, z); //x,y 對調
//cout << "Y2X="<<step2<<endl;
cout << (step1<step2? step1:step2) << endl;
因為X,Y,Z都很小, 我就用迴圈慢慢做. 每一次迴圈, 先看X要不要補水, 再看Y要不要清空, 然侯X往Y倒, 倒多少水就看Y剩下的空間和X剩下的水量中,誰比較少.
int X2Y(int x, int y, int z){
int count=0;
int cur_x=0;
int cur_y=0;
while(cur_x!=z && cur_y!=z){
if(cur_x==0){
cur_x+=x;
count++;
}
if(cur_y==y){
cur_y=0;
count++;
}
int diff_y=y-cur_y;
int SubV = (diff_y<cur_x? diff_y:cur_x);
cur_x-=SubV;
cur_y+=SubV;
count++;
}
return count;
}
完整程式碼如下.
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
int X2Y(int x, int y, int z){
int count=0;
int cur_x=0;
int cur_y=0;
while(cur_x!=z && cur_y!=z){
if(cur_x==0){
cur_x+=x;
count++;
}
if(cur_y==y){
cur_y=0;
count++;
}
int diff_y=y-cur_y;
int SubV = (diff_y<cur_x? diff_y:cur_x);
cur_x-=SubV;
cur_y+=SubV;
count++;
}
return count;
}
int main() {
int n, x, y, z;
cin >> n;
while(n--){
cin >> x >> y >> z;
if(x<y) swap(x,y);
if (x==z || y==z){
cout << "1" << endl;
continue;
}
if (z>x || z % gcd(x, y) != 0) {
cout << "-1" << endl;
continue;
}
int step1=X2Y(x, y, z);
//cout << "X2Y="<<step1<<endl;
int step2=X2Y(y, x, z);
//cout << "Y2X="<<step2<<endl;
cout << (step1<step2? step1:step2) << endl;
}
return 0;
}
