1831.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1831 on 2006-08-25 at 00:31:13 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int V[] = { 1, 5, 10, 25 };

int c[4], p;

int comp(int, int*);

int main()
{
	int cf[2][4], sum[2];

	while(scanf("%d", &p) != EOF && p != 0) {
		for(int i = 0; i < 4; i++) scanf("%d", &c[i]);
		for(int i = 0; i < 2; i++) sum[i] = comp(i, cf[i]);
		int ck = 0;
		bool can = true;
		if(sum[0] == -1 && sum[1] == -1) can = false;
		else if(sum[0] == -1) ck = 1;
		else if(sum[1] == -1) ck = 0;
		else if(sum[0] < sum[1]) ck = 1;
		if(can) printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n", cf[ck][0], cf[ck][1], cf[ck][2], cf[ck][3]);
		else printf("Charlie cannot buy coffee.\n");
	}
	
	return 0;
}

int comp(int k, int* cf)
{
	memcpy(cf, c, sizeof(c));
	int sum = 0;
	for(int i = 0; i < 4; i++) sum += c[i]*V[i];
	for(int i = 3; i >= 0; i--) {
		while(sum-p >= V[i] && cf[i] > 0) { cf[i]--; sum -= V[i]; }
		if(k == 1 && i == 3 && cf[i] != c[i]) { cf[i]++; sum += V[i]; }
	}
	if(sum != p) return -1;
	int ts = 0;
	for(int i = 0; i < 4; i++) ts += cf[i];
	return ts;
}