Submission #12132

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

typedef long long lint;
lint dp[100];

lint a,b,p,q;

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

lint f(lint x, lint y, int step){
    if(x == 0 || y == 0) return 0;
    if(x >= y){
        if(dp[step]) return dp[step];
        if(!calc_valid(q,x/y)) return dp[step] = f(y,x%y,step+1) + p;
        else return dp[step] = min(f(y,x%y,step+1) + p,f(x%y,y,step+1) + q*(x/y));
    }
    else{
        if(!calc_valid(q,y/x)) return 5e18;
        else return f(x,y%x,step+1) + q * (y/x);
    }
}

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

int main(){
    int t;
    scanf("%d",&t);
    while (t--) {
        solve();
    }
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 1196 KB Output is correct
2 Correct 0 ms 1196 KB Output is correct
3 Correct 0 ms 1196 KB Output is correct
4 Correct 0 ms 1196 KB Output is correct
5 Correct 0 ms 1196 KB Output is correct
6 Correct 0 ms 1196 KB Output is correct
7 Correct 0 ms 1196 KB Output is correct
8 Correct 0 ms 1196 KB Output is correct
9 Correct 0 ms 1196 KB Output is correct
10 Correct 0 ms 1196 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 201 ms 1196 KB Output is correct
2 Correct 199 ms 1196 KB Output is correct
3 Correct 207 ms 1196 KB Output is correct
4 Correct 201 ms 1196 KB Output is correct
5 Correct 196 ms 1196 KB Output is correct
6 Correct 194 ms 1196 KB Output is correct
7 Correct 205 ms 1196 KB Output is correct
8 Correct 198 ms 1196 KB Output is correct
9 Correct 204 ms 1196 KB Output is correct
10 Correct 201 ms 1196 KB Output is correct
11 Correct 199 ms 1196 KB Output is correct
12 Correct 195 ms 1196 KB Output is correct
13 Correct 204 ms 1196 KB Output is correct
14 Correct 0 ms 1196 KB Output is correct
15 Correct 0 ms 1196 KB Output is correct
16 Correct 2 ms 1196 KB Output is correct
17 Correct 0 ms 1196 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 1196 KB Output is correct
2 Correct 4 ms 1196 KB Output is correct
3 Correct 3 ms 1196 KB Output is correct
4 Correct 5 ms 1196 KB Output is correct
5 Correct 4 ms 1196 KB Output is correct
6 Correct 4 ms 1196 KB Output is correct
7 Correct 5 ms 1196 KB Output is correct
8 Correct 5 ms 1196 KB Output is correct
9 Correct 5 ms 1196 KB Output is correct
10 Correct 5 ms 1196 KB Output is correct
11 Correct 4 ms 1196 KB Output is correct
12 Correct 5 ms 1196 KB Output is correct
13 Correct 3 ms 1196 KB Output is correct
14 Correct 0 ms 1196 KB Output is correct
15 Correct 2 ms 1196 KB Output is correct
16 Correct 0 ms 1196 KB Output is correct
17 Correct 2 ms 1196 KB Output is correct
18 Correct 2 ms 1196 KB Output is correct
19 Correct 4 ms 1196 KB Output is correct
20 Correct 4 ms 1196 KB Output is correct
21 Correct 3 ms 1196 KB Output is correct
22 Correct 4 ms 1196 KB Output is correct
23 Correct 4 ms 1196 KB Output is correct
24 Correct 5 ms 1196 KB Output is correct
25 Correct 5 ms 1196 KB Output is correct
26 Correct 5 ms 1196 KB Output is correct
27 Correct 8 ms 1196 KB Output is correct
28 Correct 5 ms 1196 KB Output is correct
29 Correct 6 ms 1196 KB Output is correct
30 Correct 3 ms 1196 KB Output is correct
31 Correct 5 ms 1196 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 832 ms 1196 KB Output is correct
2 Correct 833 ms 1196 KB Output is correct
3 Correct 829 ms 1196 KB Output is correct
4 Correct 841 ms 1196 KB Output is correct
5 Correct 830 ms 1196 KB Output is correct
6 Correct 863 ms 1196 KB Output is correct
7 Correct 840 ms 1196 KB Output is correct
8 Correct 840 ms 1196 KB Output is correct
9 Correct 830 ms 1196 KB Output is correct
10 Correct 826 ms 1196 KB Output is correct
11 Correct 839 ms 1196 KB Output is correct
12 Correct 853 ms 1196 KB Output is correct
13 Correct 852 ms 1196 KB Output is correct
14 Correct 934 ms 1196 KB Output is correct
15 Correct 947 ms 1196 KB Output is correct
16 Correct 919 ms 1196 KB Output is correct
17 Correct 915 ms 1196 KB Output is correct
18 Correct 923 ms 1196 KB Output is correct
19 Correct 281 ms 1196 KB Output is correct
20 Correct 275 ms 1196 KB Output is correct
21 Correct 269 ms 1196 KB Output is correct
22 Correct 284 ms 1196 KB Output is correct
23 Correct 334 ms 1196 KB Output is correct
24 Correct 367 ms 1196 KB Output is correct
25 Correct 349 ms 1196 KB Output is correct
26 Correct 332 ms 1196 KB Output is correct
27 Correct 345 ms 1196 KB Output is correct
28 Correct 955 ms 1196 KB Output is correct
29 Correct 899 ms 1196 KB Output is correct
30 Correct 967 ms 1196 KB Output is correct
31 Correct 840 ms 1196 KB Output is correct
32 Correct 893 ms 1196 KB Output is correct
33 Correct 933 ms 1196 KB Output is correct
34 Correct 918 ms 1196 KB Output is correct
35 Correct 968 ms 1196 KB Output is correct