#include<stdio.h>
#define M 922337203685477580LL
int t,w;
long long x,y,p,q,dap;
struct data
{
long long x,y;
}a[101];
struct data2
{
long long mi,ma;
}d[101];
void gcd(long long x,long long y)
{
w++; a[w].x=x; a[w].y=y;
if(x%y==0) return;
gcd(y,x%y);
}
int main()
{
int i,j;
scanf("%d",&t);
for(i=1;i<=t;i++)
{
dap=M; w=0;
for(j=1;j<=100;j++) d[j].ma=M, d[j].mi=M;
scanf("%lld %lld %lld %lld",&x,&y,&p,&q);
if(x==y){
if(p>q) printf("%lld\n",q);
else printf("%lld\n",p);
continue;
}
if(x>y) gcd(x,y);
else gcd(y,x);
if(x>y) d[1].ma=0;
else d[1].mi=0, d[1].ma=p;
for(j=2;j<=w;j++)
{
if(d[j-1].ma+q*(a[j-1].x/a[j-1].y)>0 && d[j].mi>d[j-1].ma+q*(a[j-1].x/a[j-1].y)) d[j].mi=d[j-1].ma+q*(a[j-1].x/a[j-1].y);
if(d[j].ma>d[j-1].ma+p) d[j].ma=d[j-1].ma+p;
if(d[j-1].mi+q*(a[j-1].x/a[j-1].y)>0 && d[j].ma>d[j-1].mi+q*(a[j-1].x/a[j-1].y)) d[j].ma=d[j-1].mi+q*(a[j-1].x/a[j-1].y);
if(d[j].ma>d[j].mi+p) d[j].ma=d[j].mi+p;
}
if(d[w].mi+q*(a[j-1].x/a[j-1].y)>0 && dap>d[w].mi+q*(a[w].x/a[w].y)) dap=d[w].mi+q*(a[w].x/a[w].y);
if(d[w].ma+q*(a[j-1].x/a[j-1].y)>0 && dap>d[w].ma+q*(a[w].x/a[w].y)) dap=d[w].ma+q*(a[w].x/a[w].y);
if(dap>d[w].ma+p) dap=d[w].ma+p;
if(dap>d[w].mi+p+p) dap=d[w].mi+p+p;
printf("%lld\n",dap);
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
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 |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
90 ms |
1084 KB |
Output is correct |
| 2 |
Correct |
100 ms |
1084 KB |
Output is correct |
| 3 |
Correct |
97 ms |
1084 KB |
Output is correct |
| 4 |
Correct |
92 ms |
1084 KB |
Output is correct |
| 5 |
Correct |
85 ms |
1084 KB |
Output is correct |
| 6 |
Correct |
98 ms |
1084 KB |
Output is correct |
| 7 |
Correct |
76 ms |
1084 KB |
Output is correct |
| 8 |
Correct |
78 ms |
1084 KB |
Output is correct |
| 9 |
Correct |
80 ms |
1084 KB |
Output is correct |
| 10 |
Correct |
90 ms |
1084 KB |
Output is correct |
| 11 |
Correct |
103 ms |
1084 KB |
Output is correct |
| 12 |
Correct |
93 ms |
1084 KB |
Output is correct |
| 13 |
Correct |
98 ms |
1084 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1084 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 16 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1084 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
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 |
2 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 |
2 ms |
1084 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 16 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 17 |
Correct |
1 ms |
1084 KB |
Output is correct |
| 18 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 19 |
Correct |
1 ms |
1084 KB |
Output is correct |
| 20 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 21 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 22 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 23 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 24 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 25 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 26 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 27 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 28 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 29 |
Correct |
2 ms |
1084 KB |
Output is correct |
| 30 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 31 |
Correct |
1 ms |
1084 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
232 ms |
1084 KB |
Output is correct |
| 2 |
Correct |
183 ms |
1084 KB |
Output is correct |
| 3 |
Correct |
242 ms |
1084 KB |
Output is correct |
| 4 |
Correct |
213 ms |
1084 KB |
Output is correct |
| 5 |
Correct |
224 ms |
1084 KB |
Output is correct |
| 6 |
Correct |
233 ms |
1084 KB |
Output is correct |
| 7 |
Correct |
221 ms |
1084 KB |
Output is correct |
| 8 |
Correct |
230 ms |
1084 KB |
Output is correct |
| 9 |
Correct |
220 ms |
1084 KB |
Output is correct |
| 10 |
Correct |
230 ms |
1084 KB |
Output is correct |
| 11 |
Correct |
234 ms |
1084 KB |
Output is correct |
| 12 |
Correct |
242 ms |
1084 KB |
Output is correct |
| 13 |
Correct |
239 ms |
1084 KB |
Output is correct |
| 14 |
Correct |
246 ms |
1084 KB |
Output is correct |
| 15 |
Correct |
244 ms |
1084 KB |
Output is correct |
| 16 |
Correct |
217 ms |
1084 KB |
Output is correct |
| 17 |
Correct |
246 ms |
1084 KB |
Output is correct |
| 18 |
Correct |
249 ms |
1084 KB |
Output is correct |
| 19 |
Incorrect |
140 ms |
1084 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
