답안 #12127 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
12127	2014-12-21T07:45:43 Z	kriii	Min-cost GCD (GA9_mcg)	C++14	100 / 100	519 ms	1576 KB

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

long long a,b,p,q,l;

vector<pair<long long, long long> > u;

void gcd(long long a, long long b)
{
	if (a == 0 || b == 0);
	else if(a > b) gcd(b,a%b);
	else gcd(a,b%a);
	if (a < b) swap(a,b);

	u.push_back(make_pair(a,b));
	if (a != b) u.push_back(make_pair(b,a));
}

int find(vector<pair<long long, long long> > &e, int i, pair<long long, long long> p)
{
	while (i--) if (e[i] == p) return i;
	return -1;
}

int main()
{
	int T; scanf ("%d",&T); while (T--){
		scanf ("%lld %lld %lld %lld",&a,&b,&p,&q);
		u.clear(); l = 1e18 / q;
		gcd(a,b);
		vector<long long> d(u.size());
		for (int i=0;i<u.size();i++){
			if (u[i].first == 0 || u[i].second == 0) d[i] = 0;
			else if (u[i].first == u[i].second) d[i] = p < q ? p : q;
			else{
				long long na = u[i].first, nb = u[i].second;
				d[i] = p + d[find(u,i,make_pair(nb,na%nb))];
				if (na > nb){
					long long nd = na / nb, ne = q * nd;
					if (nd <= l) d[i] = min(d[i], ne+d[find(u,i,make_pair(na-nb*nd,nb))]);
				}
				else{
					long long nd = nb / na, ne = q * nd;
					if (nd <= l) d[i] = min(d[i], ne+d[find(u,i,make_pair(na,nb-na*nd))]);
				}
			}
		}
		printf ("%lld\n",d[find(u,u.size(),make_pair(a,b))]);
	}

	return 0;
}

Subtask #1
14.0 / 14.0

#	결과	메모리	Grader output
1	Correct	1576 KB	Output is correct
2	Correct	1576 KB	Output is correct
3	Correct	1576 KB	Output is correct
4	Correct	1576 KB	Output is correct
5	Correct	1576 KB	Output is correct
6	Correct	1576 KB	Output is correct
7	Correct	1576 KB	Output is correct
8	Correct	1576 KB	Output is correct
9	Correct	1576 KB	Output is correct
10	Correct	1576 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	131 ms	1576 KB	Output is correct
2	Correct	138 ms	1576 KB	Output is correct
3	Correct	146 ms	1576 KB	Output is correct
4	Correct	136 ms	1576 KB	Output is correct
5	Correct	135 ms	1576 KB	Output is correct
6	Correct	127 ms	1576 KB	Output is correct
7	Correct	133 ms	1576 KB	Output is correct
8	Correct	115 ms	1576 KB	Output is correct
9	Correct	124 ms	1576 KB	Output is correct
10	Correct	129 ms	1576 KB	Output is correct
11	Correct	131 ms	1576 KB	Output is correct
12	Correct	128 ms	1576 KB	Output is correct
13	Correct	137 ms	1576 KB	Output is correct
14	Correct	0 ms	1576 KB	Output is correct
15	Correct	0 ms	1576 KB	Output is correct
16	Correct	0 ms	1576 KB	Output is correct
17	Correct	0 ms	1576 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1576 KB	Output is correct
2	Correct	2 ms	1576 KB	Output is correct
3	Correct	0 ms	1576 KB	Output is correct
4	Correct	3 ms	1576 KB	Output is correct
5	Correct	2 ms	1576 KB	Output is correct
6	Correct	3 ms	1576 KB	Output is correct
7	Correct	0 ms	1576 KB	Output is correct
8	Correct	2 ms	1576 KB	Output is correct
9	Correct	2 ms	1576 KB	Output is correct
10	Correct	0 ms	1576 KB	Output is correct
11	Correct	3 ms	1576 KB	Output is correct
12	Correct	3 ms	1576 KB	Output is correct
13	Correct	2 ms	1576 KB	Output is correct
14	Correct	2 ms	1576 KB	Output is correct
15	Correct	0 ms	1576 KB	Output is correct
16	Correct	2 ms	1576 KB	Output is correct
17	Correct	0 ms	1576 KB	Output is correct
18	Correct	2 ms	1576 KB	Output is correct
19	Correct	3 ms	1576 KB	Output is correct
20	Correct	0 ms	1576 KB	Output is correct
21	Correct	2 ms	1576 KB	Output is correct
22	Correct	3 ms	1576 KB	Output is correct
23	Correct	3 ms	1576 KB	Output is correct
24	Correct	3 ms	1576 KB	Output is correct
25	Correct	3 ms	1576 KB	Output is correct
26	Correct	2 ms	1576 KB	Output is correct
27	Correct	3 ms	1576 KB	Output is correct
28	Correct	0 ms	1576 KB	Output is correct
29	Correct	2 ms	1576 KB	Output is correct
30	Correct	3 ms	1576 KB	Output is correct
31	Correct	2 ms	1576 KB	Output is correct

Subtask #4
43.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	415 ms	1576 KB	Output is correct
2	Correct	417 ms	1576 KB	Output is correct
3	Correct	412 ms	1576 KB	Output is correct
4	Correct	420 ms	1576 KB	Output is correct
5	Correct	417 ms	1576 KB	Output is correct
6	Correct	419 ms	1576 KB	Output is correct
7	Correct	421 ms	1576 KB	Output is correct
8	Correct	422 ms	1576 KB	Output is correct
9	Correct	415 ms	1576 KB	Output is correct
10	Correct	419 ms	1576 KB	Output is correct
11	Correct	440 ms	1576 KB	Output is correct
12	Correct	423 ms	1576 KB	Output is correct
13	Correct	447 ms	1576 KB	Output is correct
14	Correct	507 ms	1576 KB	Output is correct
15	Correct	508 ms	1576 KB	Output is correct
16	Correct	490 ms	1576 KB	Output is correct
17	Correct	503 ms	1576 KB	Output is correct
18	Correct	486 ms	1576 KB	Output is correct
19	Correct	170 ms	1576 KB	Output is correct
20	Correct	191 ms	1576 KB	Output is correct
21	Correct	174 ms	1576 KB	Output is correct
22	Correct	172 ms	1576 KB	Output is correct
23	Correct	210 ms	1576 KB	Output is correct
24	Correct	212 ms	1576 KB	Output is correct
25	Correct	217 ms	1576 KB	Output is correct
26	Correct	213 ms	1576 KB	Output is correct
27	Correct	228 ms	1576 KB	Output is correct
28	Correct	519 ms	1576 KB	Output is correct
29	Correct	482 ms	1576 KB	Output is correct
30	Correct	499 ms	1576 KB	Output is correct
31	Correct	447 ms	1576 KB	Output is correct
32	Correct	477 ms	1576 KB	Output is correct
33	Correct	516 ms	1576 KB	Output is correct
34	Correct	499 ms	1576 KB	Output is correct
35	Correct	512 ms	1576 KB	Output is correct

답안 #12127

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 16.0 / 16.0

Subtask #3 27.0 / 27.0

Subtask #4 43.0 / 43.0

Subtask #1
14.0 / 14.0

Subtask #2
16.0 / 16.0

Subtask #3
27.0 / 27.0

Subtask #4
43.0 / 43.0