oj.uz

Submission #12102

# Submission time Handle Problem Language Result Execution time Memory
12102 2014-12-21T06:56:15 Z gs14004 Min-cost GCD (GA9_mcg) C++
14 / 100
 1000 ms 1084 KB 
#include <cstdio>
typedef long long lint;

lint a,b,p,q;

bool calc_valid(lint x, lint y){
    while (y) {
        if(x > 1e17) return 0;
        x <<= 1;
        y >>= 1;
    }
    return 1;
}

lint f(lint x, lint y){
    if(x == 0 || y == 0) return 0;
    lint c1 = f(y,x%y) + p; // 결코 답안은 10^17을 넘지 않는다
    lint c2;
    if(x >= y){
        if(!calc_valid(q,x/y)) return c1;
        else c2 = f(x%y,y) + q*(x/y);
    }
    else{
        if(!calc_valid(q,y/x)) return c1;
        else c2 = f(x,y%x) + q*(y/x);
    }
    return c1 < c2 ? c1 : c2;
}

void solve(){
    scanf("%lld %lld %lld %lld",&a,&b,&p,&q);
    printf("%lld\n",f(a,b));
}

int main(){
    int t;
    scanf("%d",&t);
    while (t--) {
        solve();
    }
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1084 KB Output is correct
2 Correct 0 ms 1084 KB Output is correct
3 Correct 0 ms 1084 KB Output is correct
4 Correct 0 ms 1084 KB Output is correct
5 Correct 0 ms 1084 KB Output is correct
6 Correct 0 ms 1084 KB Output is correct
7 Correct 0 ms 1084 KB Output is correct
8 Correct 0 ms 1084 KB Output is correct
9 Correct 0 ms 1084 KB Output is correct
10 Correct 0 ms 1084 KB Output is correct

Subtask #2
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 1084 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 1084 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 1080 KB Program timed out
2 Halted 0 ms 0 KB -