2074.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2074 on 2005-11-01 at 19:36:25 */ 
#include <cstdio>
#include <cstring>

const int MAX = 512;
const int coin[4] = {25, 10, 5, 1};

class Change {
public:
	int n[4];
	bool can;
	Change() {
		n[0] = n[1] = n[2] = n[3] = 0;
		can = true;
	}
	int sum() {
		int k = 0, i;
		for(i = 0; i < 4; i++) {
			k += n[i];
		}
		return k;
	}
	void operator =(const Change& c) {
		int i;
		for(i = 0; i < 4; i++) {
			n[i] = c.n[i];
		}
	}
};

int main()
{
	double d;
	int i, j, k, m, n[4];
	Change change[MAX];
	
	while(scanf("%lf %d %d %d %d", &d, &n[0], &n[1], &n[2], &n[3]) == 5) {
		m = (int)((d+1e-4)*100);
		for(i = 0; i <= m; i++) {
			change[i].can = false;
		}
		for(i = 3; i >= 0; i--) {
			for(j = 1; j <= n[i] && j*coin[i] <= m; j++) {
				for(k = 0; k < 4; k++) {
					change[j*coin[i]].n[k] = 0;
				}
				change[j*coin[i]].n[i] = j;
				change[j*coin[i]].can = true;
			}
		}
		for(i = 1; i <= m; i++) {
			for(j = 0; j < 4; j++) {
				for(k = 0; i-k*coin[j] >= 0 && k <= n[j]-change[i-k*coin[j]].n[j]; k++) {
					if(change[i-k*coin[j]].can) {
						if(!change[i].can) {
							change[i] = change[i-k*coin[j]];
							change[i].n[j] += k;
						} else if(change[i].sum() > change[i-k*coin[j]].sum() + k) {
							change[i] = change[i-k*coin[j]];
							change[i].n[j] += k;
						}
						change[i].can = true;
					}
				}
			}
		}
		if(!change[m].can) {
			printf("NO EXACT CHANGE\n");
		} else {
			printf("%d %d %d %d\n", change[m].n[0], change[m].n[1], 
				change[m].n[2], change[m].n[3]);
		}
	}
	
	return 0;
}