| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 12096 |
2014-12-21T05:32:08 Z |
ainu7 |
Min-cost GCD (GA9_mcg) |
C++ |
|
1000 ms |
1720 KB |
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;
struct state {
long long a, b, cost;
state(long long _a, long long _b, long long _cost) {
cost = _cost;
a = _a;
b = _b;
};
bool operator < (const state & another) const {
if (cost != another.cost) return cost < another.cost;
if (a != another.a) return a < another.a;
return b < another.b;
}
};
int main()
{
int T;
cin >> T;
for (int i=0; i<T; i++) {
long long a, b, p, q;
cin >> a >> b >> p >> q;
set<state> S;
S.insert(state(a, b, 0));
long long res = 1LL<<62;
set<pair<long long, long long> > seen;
while (1) {
set<state>::iterator it = S.begin();
state now = *it;
S.erase(it);
if (seen.find(pair<long long, long long>(now.a, now.b)) != seen.end()) continue;
seen.insert(pair<long long, long long>(now.a, now.b));
if (now.a == 0 || now.b == 0) {
res = now.cost;
break;
}
S.insert(state(now.b, now.a%now.b, now.cost+p));
if (now.a >= now.b) {
long long c = now.a / now.b;
if (1.0*c*q < (1LL<<62))
S.insert(state(now.a%now.b, now.b, now.cost+c*q));
} else {
long long c = now.b / now.a;
if (1.0*c*q < (1LL<<62)) {
S.insert(state(now.a, now.b%now.a, now.cost+c*q));
}
}
}
cout << res << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1720 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1720 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1720 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1720 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1720 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1720 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1720 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1720 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1720 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
560 ms |
1720 KB |
Output is correct |
| 2 |
Correct |
768 ms |
1720 KB |
Output is correct |
| 3 |
Correct |
873 ms |
1720 KB |
Output is correct |
| 4 |
Correct |
791 ms |
1720 KB |
Output is correct |
| 5 |
Correct |
562 ms |
1720 KB |
Output is correct |
| 6 |
Correct |
800 ms |
1720 KB |
Output is correct |
| 7 |
Correct |
768 ms |
1720 KB |
Output is correct |
| 8 |
Correct |
679 ms |
1720 KB |
Output is correct |
| 9 |
Correct |
735 ms |
1720 KB |
Output is correct |
| 10 |
Correct |
671 ms |
1720 KB |
Output is correct |
| 11 |
Correct |
797 ms |
1720 KB |
Output is correct |
| 12 |
Correct |
592 ms |
1720 KB |
Output is correct |
| 13 |
Correct |
748 ms |
1720 KB |
Output is correct |
| 14 |
Correct |
11 ms |
1720 KB |
Output is correct |
| 15 |
Correct |
9 ms |
1720 KB |
Output is correct |
| 16 |
Correct |
9 ms |
1720 KB |
Output is correct |
| 17 |
Correct |
9 ms |
1720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
1720 KB |
Output is correct |
| 2 |
Correct |
24 ms |
1720 KB |
Output is correct |
| 3 |
Correct |
8 ms |
1720 KB |
Output is correct |
| 4 |
Correct |
22 ms |
1720 KB |
Output is correct |
| 5 |
Correct |
21 ms |
1720 KB |
Output is correct |
| 6 |
Correct |
19 ms |
1720 KB |
Output is correct |
| 7 |
Correct |
14 ms |
1720 KB |
Output is correct |
| 8 |
Correct |
16 ms |
1720 KB |
Output is correct |
| 9 |
Correct |
17 ms |
1720 KB |
Output is correct |
| 10 |
Correct |
24 ms |
1720 KB |
Output is correct |
| 11 |
Correct |
18 ms |
1720 KB |
Output is correct |
| 12 |
Correct |
19 ms |
1720 KB |
Output is correct |
| 13 |
Correct |
19 ms |
1720 KB |
Output is correct |
| 14 |
Correct |
9 ms |
1720 KB |
Output is correct |
| 15 |
Correct |
7 ms |
1720 KB |
Output is correct |
| 16 |
Correct |
14 ms |
1720 KB |
Output is correct |
| 17 |
Correct |
6 ms |
1720 KB |
Output is correct |
| 18 |
Correct |
11 ms |
1720 KB |
Output is correct |
| 19 |
Correct |
0 ms |
1720 KB |
Output is correct |
| 20 |
Correct |
31 ms |
1720 KB |
Output is correct |
| 21 |
Correct |
21 ms |
1720 KB |
Output is correct |
| 22 |
Correct |
19 ms |
1720 KB |
Output is correct |
| 23 |
Correct |
21 ms |
1720 KB |
Output is correct |
| 24 |
Correct |
18 ms |
1720 KB |
Output is correct |
| 25 |
Correct |
25 ms |
1720 KB |
Output is correct |
| 26 |
Correct |
20 ms |
1720 KB |
Output is correct |
| 27 |
Correct |
20 ms |
1720 KB |
Output is correct |
| 28 |
Correct |
22 ms |
1720 KB |
Output is correct |
| 29 |
Correct |
16 ms |
1720 KB |
Output is correct |
| 30 |
Correct |
41 ms |
1720 KB |
Output is correct |
| 31 |
Correct |
11 ms |
1720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1000 ms |
0 KB |
Program timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
