Submission #27210

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
27210	2017-07-10 16:00:42	TAMREF	Min-cost GCD (GA9_mcg)	C++11	100 / 100	326 ms	2024 KiB

mcg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mx=300;
ll x,y,p,q;
ll eu[mx], dp[2*mx];
int E;
void workgcd(ll u, ll v){
    eu[E++]=v;
    if(!v) return;
    workgcd(v,u%v);
}
int main(){
    int T;
    for(scanf("%d",&T);T--;){
        scanf("%lld%lld%lld%lld",&x,&y,&p,&q);
        E=0;
        fill(dp,dp+2*mx,0);
        eu[E++]=max(x,y);
        workgcd(max(x,y),min(x,y));
        for(int i=E-3;i>=0;i--){
            if((double)(p+dp[2*i+2]-dp[2*i+3])/q<eu[i]/eu[i+1]) dp[2*i]=dp[2*i+2]+p;
            else dp[2*i]=dp[2*i+3]+q*(eu[i]/eu[i+1]);
            if((double)(p+dp[2*i]-dp[2*i+2])/q<eu[i]/eu[i+1]) dp[2*i+1]=dp[2*i]+p;
            else dp[2*i+1]=dp[2*i+2]+q*(eu[i]/eu[i+1]);
        }
        printf("%lld\n",x>=y?dp[0]:dp[1]);
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

mcg.cpp: In function 'int main()':
mcg.cpp:15:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%d",&T);T--;){
                       ^
mcg.cpp:16:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld%lld",&x,&y,&p,&q);
                                              ^

• Subtask 1: 14 / 14
• Subtask 2: 16 / 16
• Subtask 3: 27 / 27
• Subtask 4: 43 / 43