oj.uz

Submission #12129

# Submission time Handle Problem Language Result Execution time Memory
12129 2014-12-21T07:46:53 Z gs14004 Min-cost GCD (GA9_mcg) C++
0 / 100
 1000 ms 1196 KB 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long lint;

lint a,b,p,q;

bool calc_valid(lint x, lint y){
    double t = log10(x)+log10(y);
    return t < 18;
}

lint f(lint x, lint y){
    if(x == 0 || y == 0) return 0;
    if(x >= y){
        lint cost1 = 2 * p;
        lint cost2 = 0;
        if(!calc_valid(q,x/y)) cost2 = 5e18;
        else cost2 = q * (x/y);
        if(x%y){
            if(!calc_valid(q,y/(x%y))) cost2 = 5e18;
            else cost2 += q * (y/(x%y));
        }
        else cost1 = p;
        if(cost1 <= cost2) return f(y,x%y) + p;
        else return f(x%y,y) + q*(x/y);
    }
    else{
        if(!calc_valid(q,y/x)) return 5e18;
        else return f(x,y%x) + q * (y/x);
    }
}

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

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

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1196 KB Output is correct
2 Incorrect 0 ms 1196 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 1196 KB Output is correct
2 Correct 259 ms 1196 KB Output is correct
3 Correct 254 ms 1196 KB Output is correct
4 Incorrect 227 ms 1196 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 43.0

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