oj.uz

답안 #12247

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
12247 2014-12-25T20:11:04 Z pro0331 Min-cost GCD (GA9_mcg) C++
30 / 100
 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));
	}
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 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

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 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

Subtask #3
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1000 ms 1212 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1000 ms 1212 KB Program timed out
2 Halted 0 ms 0 KB -