SPOJ 25 - Pouring water[POUR1]

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

这道题看上去有点欧几里得算法的意思在里面,实际上不是。我仅仅是在判断有没有解的时候用了一次求最大公约数的算法,接下来就是模拟,分别模拟从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;
}

Your program in C++ from 2010-04-09 07:16:22 ran for 0.01 seconds and used 2536 KB of memory.


本作品遵循“署名-非商业性使用-相同方式共享 3.0 Unported”协议,转载请注明来自richard-desktop
Creative Commons License

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter