oj.uz

Submission #12073

# Submission time Handle Problem Language Result Execution time Memory
12073 2014-12-20T21:14:57 Z ainta Min-cost GCD (GA9_mcg) C++
0 / 100
 243 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));
	}
}

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 90 ms 1084 KB Output is correct
2 Incorrect 84 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 2 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 243 ms 1084 KB Output isn't correct
2 Halted 0 ms 0 KB -