OpenJudge/1384.cpp at master · tongtzeho/OpenJudge · 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
#include <iostream>
#include <algorithm>
using namespace std;

struct COIN
{
	int p, w;
}coin[605];

bool cmp(const COIN &c1, const COIN &c2)
{
	return (c1.p*1.0/c1.w < c2.p*1.0/c2.w);
}

int answer[2][10050];

int main()
{
	int testcase;
	cin >> testcase;
	while (testcase > 0)
	{
		testcase--;
		int e, f, n, i, j;
		cin >> e >> f >> n;
		for (i = 0; i < n; i++)
		{
			cin >> coin[i].p >> coin[i].w;
		}
		sort(coin, coin+n, cmp);
		for (j = 0; j <= f-e; j++)
			answer[0][j] = answer[1][j] = -1;
		for (j = 0; j <= f-e; j++)
			if (j % coin[n-1].w == 0)
			{
				answer[(n-1)%2][j] = coin[n-1].p*(j/coin[n-1].w);
			}
		for (i = n-2; i >= 0; i--)
			for (j = 0; j <= f-e; j++)
			{
				int put = -1, skip = -1;
				if (j >= coin[i].w && answer[i%2][j-coin[i].w] != -1)
				{
					put = coin[i].p+answer[i%2][j-coin[i].w];
				}
				if (answer[(i+1)%2][j] != -1)
				{
					skip = answer[(i+1)%2][j];
				}
				answer[i%2][j] = put;
				if (skip != -1 && (skip < put || put == -1))
				{
					answer[i%2][j] = skip;
				}
			}
		if (answer[0][f-e] != -1)
		{
			cout << "The minimum amount of money in the piggy-bank is " << answer[0][f-e] << "." << endl;
		}
		else
		{
			cout << "This is impossible." << endl;
		}
	}
	return 0;
}