| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 12074 |
2014-12-20T21:17:03 Z |
ainta |
Min-cost GCD (GA9_mcg) |
C++ |
|
284 ms |
1084 KB |
#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
#define INF 999999999999999999LL
using namespace std;
long long a, b, sub, mod, C1, C2, TC1, TC2;
long long Mul(long long a, long long b){
if (a && INF / a < b)return INF;
return a*b;
}
int main()
{
int T;
scanf("%d", &T);
while (T--){
scanf("%lld%lld", &a, &b);
scanf("%lld%lld", &mod, &sub);
C1 = 0, C2 = INF;
while (a && b){
if (a == b){
C1 = C1 + min(sub, mod);
C2 = C2 + min(sub, mod);
a -= b;
continue;
}
if (a < b){
if (C2 > C1 + mod)C2 = C1 + mod;
TC1 = min(C2 + mod, C1 + Mul(b / a, sub));
TC2 = min(C2 + Mul(b / a,sub), TC1 + mod);
b = b%a;
}
else{
if (C1 > C2 + mod)C1 = C2 + mod;
TC2 = min(C1 + mod, C2 + Mul(a / b, sub));
TC1 = min(C1 + Mul(a / b,sub), TC2 + mod);
a = a%b;
}
C1 = TC1, C2 = TC2;
}
printf("%lld\n", min(C1, C2));
}
}
| # |
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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
1084 KB |
Output is correct |
| 2 |
Correct |
90 ms |
1084 KB |
Output is correct |
| 3 |
Correct |
91 ms |
1084 KB |
Output is correct |
| 4 |
Correct |
91 ms |
1084 KB |
Output is correct |
| 5 |
Correct |
91 ms |
1084 KB |
Output is correct |
| 6 |
Correct |
89 ms |
1084 KB |
Output is correct |
| 7 |
Correct |
66 ms |
1084 KB |
Output is correct |
| 8 |
Correct |
57 ms |
1084 KB |
Output is correct |
| 9 |
Correct |
73 ms |
1084 KB |
Output is correct |
| 10 |
Correct |
77 ms |
1084 KB |
Output is correct |
| 11 |
Correct |
94 ms |
1084 KB |
Output is correct |
| 12 |
Correct |
76 ms |
1084 KB |
Output is correct |
| 13 |
Correct |
91 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 |
1 ms |
1084 KB |
Output is correct |
| 17 |
Correct |
1 ms |
1084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1084 KB |
Output is correct |
| 2 |
Correct |
1 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 |
2 ms |
1084 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1084 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1084 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1084 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 13 |
Correct |
2 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 |
0 ms |
1084 KB |
Output is correct |
| 20 |
Correct |
2 ms |
1084 KB |
Output is correct |
| 21 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 22 |
Correct |
1 ms |
1084 KB |
Output is correct |
| 23 |
Correct |
1 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 |
1 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 |
0 ms |
1084 KB |
Output is correct |
| 30 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 31 |
Correct |
0 ms |
1084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
254 ms |
1084 KB |
Output is correct |
| 2 |
Correct |
201 ms |
1084 KB |
Output is correct |
| 3 |
Correct |
245 ms |
1084 KB |
Output is correct |
| 4 |
Correct |
246 ms |
1084 KB |
Output is correct |
| 5 |
Correct |
249 ms |
1084 KB |
Output is correct |
| 6 |
Correct |
252 ms |
1084 KB |
Output is correct |
| 7 |
Correct |
234 ms |
1084 KB |
Output is correct |
| 8 |
Correct |
235 ms |
1084 KB |
Output is correct |
| 9 |
Correct |
238 ms |
1084 KB |
Output is correct |
| 10 |
Correct |
247 ms |
1084 KB |
Output is correct |
| 11 |
Correct |
229 ms |
1084 KB |
Output is correct |
| 12 |
Correct |
248 ms |
1084 KB |
Output is correct |
| 13 |
Correct |
248 ms |
1084 KB |
Output is correct |
| 14 |
Correct |
274 ms |
1084 KB |
Output is correct |
| 15 |
Correct |
273 ms |
1084 KB |
Output is correct |
| 16 |
Correct |
271 ms |
1084 KB |
Output is correct |
| 17 |
Correct |
255 ms |
1084 KB |
Output is correct |
| 18 |
Correct |
252 ms |
1084 KB |
Output is correct |
| 19 |
Correct |
130 ms |
1084 KB |
Output is correct |
| 20 |
Correct |
126 ms |
1084 KB |
Output is correct |
| 21 |
Correct |
119 ms |
1084 KB |
Output is correct |
| 22 |
Correct |
131 ms |
1084 KB |
Output is correct |
| 23 |
Correct |
129 ms |
1084 KB |
Output is correct |
| 24 |
Correct |
157 ms |
1084 KB |
Output is correct |
| 25 |
Correct |
130 ms |
1084 KB |
Output is correct |
| 26 |
Correct |
144 ms |
1084 KB |
Output is correct |
| 27 |
Correct |
148 ms |
1084 KB |
Output is correct |
| 28 |
Correct |
284 ms |
1084 KB |
Output is correct |
| 29 |
Correct |
253 ms |
1084 KB |
Output is correct |
| 30 |
Correct |
258 ms |
1084 KB |
Output is correct |
| 31 |
Correct |
239 ms |
1084 KB |
Output is correct |
| 32 |
Correct |
261 ms |
1084 KB |
Output is correct |
| 33 |
Correct |
273 ms |
1084 KB |
Output is correct |
| 34 |
Correct |
262 ms |
1084 KB |
Output is correct |
| 35 |
Correct |
273 ms |
1084 KB |
Output is correct |
