algo/10306.cpp at master · AndreeaMusat/algo · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*
	Author: Andreea Musat
	Date: 15 sept 2017

	Coin change variant

	https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1247
*/

#include <bits/stdc++.h>
using namespace std;

int dp[310][310];
int sum;

inline int sq(int x, int y)
{
	return x * x + y * y;
}

int coinChange(const vector<pair<int, int>>& coins, int x, int y)
{
	if (sum - sq(x, y) < 0)
		return INT_MAX;

	if (sum - sq(x, y) == 0)
		return 0;

	int& ans = dp[x][y];
	if (ans != -1)
		return ans;

	ans = INT_MAX;

	for (size_t i = 0; i < coins.size(); i++)
	{
		int res = coinChange(coins, x + coins[i].first, y + coins[i].second);
		if (res != INT_MAX)
			ans = min(ans, 1 + res);
	}

	return ans;
}

int main()
{
	int n, m, s;
	vector<pair<int, int>> coins;
	cin >> n;

	while (n--)
	{
		cin >> m >> s;

		if (coins.size() > 0)
			coins.clear();
		coins.resize(m);

		memset(dp, -1, sizeof dp);

		for (int i = 0; i < m; i++)
			cin >> coins[i].first >> coins[i].second;

		sum = s * s;
		int res = coinChange(coins, 0, 0);
		if (res != INT_MAX)
			cout << res << "\n";
		else
			cout << "not possible\n";
	}
}