oj.uz

Submission #12782

# Submission time Handle Problem Language Result Execution time Memory
12782 2015-01-03T13:04:35 Z Qwaz Min-cost GCD (GA9_mcg) C++
0 / 100
 464 ms 1084 KB 
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long ll;

const int MAX = 70;
const ll INF = 1234567890123456789LL;

ll p, q, memo[MAX][2];

ll minGcd(ll a, ll b, int level){
	if(a == 0 || b == 0) return 0;

	ll &now = a >= b ? memo[level][0] : memo[level][1];

	if(now != 0) return now;

	if(a >= b){
		now = minGcd(b, a%b, level+1)+p;

		int count = (a - (a%b))/b;
		if((INF - minGcd(a%b, b, level+1))/count <= q)
			now = min(now, minGcd(a%b, b, level+1) + q*count);
	} else {
		now = minGcd(b, a, level)+p;

		int count = (b - (b%a))/a;
		if((INF - minGcd(a, b%a, level+1))/count <= q)
			now = min(now, minGcd(a, b%a, level+1) + q*count);
	}

	return now;
}

void reset(){
	for(int i = 0; i < MAX; i++)
		memo[i][0] = memo[i][1] = 0;
}

int main(){
	int t;
	for(scanf("%d", &t); t--;){
		ll a, b;
		scanf("%lld%lld%lld%lld", &a, &b, &p, &q);

		printf("%lld\n", minGcd(a, b, 0));

		reset();
	}

	return 0;
}

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 1084 KB Output is correct
2 Incorrect 129 ms 1084 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 464 ms 1084 KB Output isn't correct
2 Halted 0 ms 0 KB -