29592023-02-06 08:24:19bzsofiaFőzet készítéscpp11Time limit exceeded 0/50462ms6480 KiB
#include <iostream>
#include <vector>

using namespace std;

int i, j, a, b, t;

int gcd(int x, int y)
{
	while (x != 0 && y != 0)
	{
		if (x <= y) y %= x;
		else x %= y;
	}

	return x + y;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	vector<vector<int>> dp(501, vector<int>(501, 0));

	for (i = 1; i < 32; ++i)
	{
		for (j = 1; j < 32; ++j)
		{
			if (gcd(i, j) == 1)
			{
				for (a = 500; a >= i; --a)
				{
					for (b = 500; b >= j; --b)
					{
						dp[a][b] = max(dp[a][b], dp[a - i][b - j] + 1);
					}
				}
			}
		}
	}

	cin >> t;
	for (i = 1; i <= t; ++i)
	{
		cin >> a >> b;
		cout << dp[a][b] << "\n";
	}
	return 0;
}
/*
3
4 4
2 3
2 2
*/
SubtaskSumTestVerdictTimeMemory
base0/50
1Time limit exceeded0/0460ms3628 KiB
2Time limit exceeded0/0458ms4092 KiB
3Time limit exceeded0/3458ms4308 KiB
4Time limit exceeded0/2460ms4284 KiB
5Time limit exceeded0/3458ms4536 KiB
6Time limit exceeded0/2458ms4836 KiB
7Time limit exceeded0/3458ms4928 KiB
8Time limit exceeded0/2458ms5144 KiB
9Time limit exceeded0/3458ms5224 KiB
10Time limit exceeded0/2460ms5460 KiB
11Time limit exceeded0/2460ms5620 KiB
12Time limit exceeded0/2458ms5660 KiB
13Time limit exceeded0/2458ms5812 KiB
14Time limit exceeded0/2460ms5648 KiB
15Time limit exceeded0/2462ms5864 KiB
16Time limit exceeded0/2458ms5972 KiB
17Time limit exceeded0/2460ms6128 KiB
18Time limit exceeded0/2460ms6416 KiB
19Time limit exceeded0/2460ms5008 KiB
20Time limit exceeded0/3460ms6480 KiB
21Time limit exceeded0/3458ms6352 KiB
22Time limit exceeded0/3456ms4776 KiB
23Time limit exceeded0/3458ms6476 KiB