29592023-02-06 08:24:19bzsofiaFőzet készítéscpp11Időlimit túllépés 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
*/
RészfeladatÖsszpontTesztVerdiktIdőMemória
base0/50
1Időlimit túllépés0/0460ms3628 KiB
2Időlimit túllépés0/0458ms4092 KiB
3Időlimit túllépés0/3458ms4308 KiB
4Időlimit túllépés0/2460ms4284 KiB
5Időlimit túllépés0/3458ms4536 KiB
6Időlimit túllépés0/2458ms4836 KiB
7Időlimit túllépés0/3458ms4928 KiB
8Időlimit túllépés0/2458ms5144 KiB
9Időlimit túllépés0/3458ms5224 KiB
10Időlimit túllépés0/2460ms5460 KiB
11Időlimit túllépés0/2460ms5620 KiB
12Időlimit túllépés0/2458ms5660 KiB
13Időlimit túllépés0/2458ms5812 KiB
14Időlimit túllépés0/2460ms5648 KiB
15Időlimit túllépés0/2462ms5864 KiB
16Időlimit túllépés0/2458ms5972 KiB
17Időlimit túllépés0/2460ms6128 KiB
18Időlimit túllépés0/2460ms6416 KiB
19Időlimit túllépés0/2460ms5008 KiB
20Időlimit túllépés0/3460ms6480 KiB
21Időlimit túllépés0/3458ms6352 KiB
22Időlimit túllépés0/3456ms4776 KiB
23Időlimit túllépés0/3458ms6476 KiB