AOJ_1028 ICPC: Ideal Coin Payment and Change

問題
解法
代金をpとすると,実際に払う金額Pは p <= P <= p+500 の範囲にあるはず.
だから,全部ためしていくといい.

#include <cstdio>
#include <algorithm>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
const int INF = 1 << 30;
const int coin[6] = { 1, 5, 10, 50, 100, 500 };
int N[6];
int p;

int solve(int p){
	int n[6], res = 0;
	REP(i,6) n[i] = N[i];
	while(true){
		if(p == 0) break;
		bool f = true;
		for(int i = 5; i >= 0; i--){
			if(p >= coin[i] && n[i] > 0){
				n[i]--;
				p -= coin[i];
				res++;
				f = false;
				break;
			}
		}
		if(f) return INF;
	}
	return res;
}
int change(int d){
	int res = 0;
	REP(i,6){
		res += d / coin[5-i];
		d = d % coin[5-i];
	}
	return res;
}
int main(){
	while(scanf("%d", &p) && p){
		REP(i,6) scanf("%d", &N[i]);
		int ans = INF;
		for(int P = p; P <= p + 500; P++){
			ans = min(ans, solve(P) + change(P - p));;
		}
		printf("%d\n", ans);
	}
	return 0;
}