SPOJ 25 - Pouring water[POUR1]

张文泰 posted @ 2010年4月09日 21:27 in Art of Science with tags SPOJ , 4803 阅读

这道题看上去有点欧几里得算法的意思在里面，实际上不是。我仅仅是在判断有没有解的时候用了一次求最大公约数的算法，接下来就是模拟，分别模拟从a往b倒和从b往a倒得两种情况，很容易就Accepted了。

#include <cstdio>
#include <climits>

using namespace std;

int ntest,a,b,c,d;

int min(int a,int b) {
    return a<b?a:b;
}

int gcd(int a,int b) {
    return b==0?a:gcd(b,a%b);
}

int check(int a,int b) {
    int ret = 0,ca = 0,cb = 0;
    for (;;) {
        if (ca==c || cb==c) return ret;
        if (cb==b) cb = 0;
        else if (ca==0) ca = a;
        else {
            int dt = min(b-cb,ca);
            ca -= dt; cb += dt;
        }
        ret++;
    }
}

int main() {
    scanf("%d",&ntest);
    while (ntest--) {
        scanf("%d%d%d",&a,&b,&c);
        d = gcd(a,b);
        if (c%d!=0 || c>a && c>b) printf("-1\n");
        else {
            int ans = check(a,b);
            ans = min(ans,check(b,a));
            printf("%d\n",ans);
        }
    }
    return 0;
}