| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 12075 |
2014-12-20T21:49:21 Z |
ainta |
Min-cost GCD (GA9_mcg) |
C++ |
|
272 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 |
81 ms |
1084 KB |
Output is correct |
| 2 |
Correct |
90 ms |
1084 KB |
Output is correct |
| 3 |
Correct |
88 ms |
1084 KB |
Output is correct |
| 4 |
Correct |
93 ms |
1084 KB |
Output is correct |
| 5 |
Correct |
86 ms |
1084 KB |
Output is correct |
| 6 |
Correct |
91 ms |
1084 KB |
Output is correct |
| 7 |
Correct |
92 ms |
1084 KB |
Output is correct |
| 8 |
Correct |
93 ms |
1084 KB |
Output is correct |
| 9 |
Correct |
78 ms |
1084 KB |
Output is correct |
| 10 |
Correct |
79 ms |
1084 KB |
Output is correct |
| 11 |
Correct |
91 ms |
1084 KB |
Output is correct |
| 12 |
Correct |
87 ms |
1084 KB |
Output is correct |
| 13 |
Correct |
90 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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1084 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1084 KB |
Output is correct |
| 4 |
Correct |
1 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 |
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 |
0 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 |
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 |
| 18 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 19 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 20 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 21 |
Correct |
1 ms |
1084 KB |
Output is correct |
| 22 |
Correct |
2 ms |
1084 KB |
Output is correct |
| 23 |
Correct |
2 ms |
1084 KB |
Output is correct |
| 24 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 25 |
Correct |
2 ms |
1084 KB |
Output is correct |
| 26 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 27 |
Correct |
1 ms |
1084 KB |
Output is correct |
| 28 |
Correct |
2 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 |
1 ms |
1084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
232 ms |
1084 KB |
Output is correct |
| 2 |
Correct |
232 ms |
1084 KB |
Output is correct |
| 3 |
Correct |
239 ms |
1084 KB |
Output is correct |
| 4 |
Correct |
234 ms |
1084 KB |
Output is correct |
| 5 |
Correct |
231 ms |
1084 KB |
Output is correct |
| 6 |
Correct |
249 ms |
1084 KB |
Output is correct |
| 7 |
Correct |
242 ms |
1084 KB |
Output is correct |
| 8 |
Correct |
247 ms |
1084 KB |
Output is correct |
| 9 |
Correct |
242 ms |
1084 KB |
Output is correct |
| 10 |
Correct |
240 ms |
1084 KB |
Output is correct |
| 11 |
Correct |
237 ms |
1084 KB |
Output is correct |
| 12 |
Correct |
234 ms |
1084 KB |
Output is correct |
| 13 |
Correct |
247 ms |
1084 KB |
Output is correct |
| 14 |
Correct |
255 ms |
1084 KB |
Output is correct |
| 15 |
Correct |
260 ms |
1084 KB |
Output is correct |
| 16 |
Correct |
269 ms |
1084 KB |
Output is correct |
| 17 |
Correct |
254 ms |
1084 KB |
Output is correct |
| 18 |
Correct |
268 ms |
1084 KB |
Output is correct |
| 19 |
Correct |
155 ms |
1084 KB |
Output is correct |
| 20 |
Correct |
113 ms |
1084 KB |
Output is correct |
| 21 |
Correct |
136 ms |
1084 KB |
Output is correct |
| 22 |
Correct |
131 ms |
1084 KB |
Output is correct |
| 23 |
Correct |
145 ms |
1084 KB |
Output is correct |
| 24 |
Correct |
154 ms |
1084 KB |
Output is correct |
| 25 |
Correct |
130 ms |
1084 KB |
Output is correct |
| 26 |
Correct |
142 ms |
1084 KB |
Output is correct |
| 27 |
Correct |
136 ms |
1084 KB |
Output is correct |
| 28 |
Correct |
270 ms |
1084 KB |
Output is correct |
| 29 |
Correct |
183 ms |
1084 KB |
Output is correct |
| 30 |
Correct |
254 ms |
1084 KB |
Output is correct |
| 31 |
Correct |
232 ms |
1084 KB |
Output is correct |
| 32 |
Correct |
204 ms |
1084 KB |
Output is correct |
| 33 |
Correct |
263 ms |
1084 KB |
Output is correct |
| 34 |
Correct |
272 ms |
1084 KB |
Output is correct |
| 35 |
Correct |
253 ms |
1084 KB |
Output is correct |
