POJ3040

Posted on | In ,

Allowance

Solution sketch

The sentence each denomination of coin evenly divides the next-larger denomination is a good lead for you to safely assume that using greedy strategy is fine.

If the coin value is greater than $C$, then there is no need to combine two coins into one. Just distribute them out.

For all other remaining coin values, use greedy strategy (just like coin change), and start with the largest coin value to try to get the total value as close to $C$ using minimal coins as possible. If the total value we can get is not exactly $C$, then we run the greedy algorithm from the smallest coin to the largest one. There is a little trick though, $min(\frac{remaining\ value + current\ coin\ value\ - 1}{current\ coin\ value}, all\ remaining\ coins\ for\ this\ coin\ value)$ can get you the minimal amount of coins by exceeding $C$ no more than the value of the minimal coin value that still have coins available.

This tutorial have a casual prove on this method.

AC code

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cstring>
#include <climits>
using namespace std;
typedef pair<int, int> ii;
typedef long long ll;
int main()
{
	int types, target;
	scanf("%d %d", &types, &target);
	vector<ii> coins;
	ll total = 0;
	for (int i = 0; i < types; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		coins.push_back(ii(a, b));
		total += (ll)a * b;
	}
	sort(coins.begin(), coins.end());
	reverse(coins.begin(), coins.end());
	int res = 0;
	// if the coin value is greater than the target value, just distribute it
	for(int i = 0; i < types; i++) {
		if(coins[i].first >= target) {
			res += coins[i].second;
			coins[i].second = 0;
		}			
	}
	while(true) {
		// greedy: coin change
		int used[types];
		memset(used, 0, sizeof(used));
		int remaining = target;
		for(int i = 0; i < types && remaining > 0; i++) {
			if(coins[i].second > 0) {
				used[i] = min(remaining / coins[i].first, coins[i].second); // be aware of the condition
				remaining -= used[i] * coins[i].first;
			}
		}
		// if the remaining > 0, greedy: from small to largest
		if(remaining > 0) {
			for(int i = types - 1; remaining > 0 && i >= 0; i--) {
				if(coins[i].second > 0) {
					int cnt = min( (remaining + coins[i].first - 1) / coins[i].first, coins[i].second - used[i]);
					used[i] += cnt;
					remaining -= cnt * coins[i].first;
				}
			}
		}
		if(remaining > 0)
			break;
		int mn = INT_MAX;
		for(int i = 0; i < types; i++) {
			if(coins[i].second > 0 && used[i] > 0)
				mn = min(mn, coins[i].second / used[i]);
		}
		for(int i = 0; i < types; i++) {
			if(coins[i].second > 0 && used[i] > 0)
				coins[i].second -= used[i] * mn;
		}
		res += mn;
	}
	printf("%d\n", res);
	return 0;
}