| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 12247 |
2014-12-25T20:11:04 Z |
pro0331 |
Min-cost GCD (GA9_mcg) |
C++ |
|
1000 ms |
1212 KB |
#include <stdio.h>
#include <map>
struct pair {
long long x;
long long y;
bool operator <(const pair&a) const {return ((x < a.x) || (x == a.x && y < a.y));}
};
std::map<pair, long long> cache;
long long limit;
void do_sh(pair &in, pair &out)
{
out.x = in.y;
out.y = in.x % in.y;
}
void do_ss(pair &in, pair &out)
{
if (in.x >= in.y) {
out.x = in.x - in.y;
out.y = in.y;
} else {
out.x = in.x;
out.y = in.y - in.x;
}
}
long long cost(pair &x, long long p, long long q, long long cur_cost)
{
if (x.x == 0 || x.y == 0)
return cur_cost;
std::map<pair, long long>::iterator it = cache.find(x);
long long ret;
long long cost_sh = 0, cost_ss = 0;
pair t;
if (it != cache.end()) {
ret = it->second + cur_cost;
goto RET;
}
if (cur_cost + p <= limit) {
do_sh(x, t);
cost_sh = cost(t, p, q, cur_cost + p);
}
if (cur_cost + q <= limit) {
do_ss(x, t);
cost_ss = cost(t, p, q, cur_cost + q);
}
if (cost_sh && cost_ss) {
ret = (cost_sh < cost_ss)? cost_sh : cost_ss;
cache[x] = ret - cur_cost;
} else if (cost_sh) {
ret = cost_sh;
} else if (cost_ss) {
ret = cost_ss;
} else {
return 0;
}
RET:
if (ret <= limit) {
limit = ret;
return ret;
} else {
return 0;
}
}
long long check_limit(pair &x, long long p)
{
limit = 0;
pair i1, i2;
for (i1 = x; i1.x && i1.y; limit += p) {
do_sh(i1, i2);
i1 = i2;
}
}
int main()
{
int T;
pair i;
long long p, q;
for (scanf("%d", &T); T; T--) {
cache.clear();
scanf("%lld%lld%lld%lld", &i.x, &i.y, &p, &q);
check_limit(i, p);
printf("%llu\n", cost(i, p, q, 0));
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
1212 KB |
Output is correct |
| 2 |
Correct |
429 ms |
1212 KB |
Output is correct |
| 3 |
Correct |
524 ms |
1212 KB |
Output is correct |
| 4 |
Correct |
757 ms |
1212 KB |
Output is correct |
| 5 |
Correct |
79 ms |
1212 KB |
Output is correct |
| 6 |
Correct |
822 ms |
1212 KB |
Output is correct |
| 7 |
Correct |
715 ms |
1212 KB |
Output is correct |
| 8 |
Correct |
91 ms |
1212 KB |
Output is correct |
| 9 |
Correct |
483 ms |
1212 KB |
Output is correct |
| 10 |
Correct |
100 ms |
1212 KB |
Output is correct |
| 11 |
Correct |
272 ms |
1212 KB |
Output is correct |
| 12 |
Correct |
65 ms |
1212 KB |
Output is correct |
| 13 |
Correct |
205 ms |
1212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 15 |
Correct |
3 ms |
1212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1000 ms |
1212 KB |
Program timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1000 ms |
1212 KB |
Program timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
