(DP6.1.2.1)UVA 147 Dollars(子集和有关问题)

(DP6.1.2.1)UVA 147 Dollars(子集和问题)

/*
 * UVA_147.cpp
 *
 *  Created on: 2013年10月12日
 *      Author: Administrator
 */


#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 6005;
int b[11] = {1,2,4,10,20,40,100,200,400,1000,2000};
long long a[maxn];

int main(){
	double n;

	int i,j;
	for(i = 0 ; i <= 6000 ; ++i){
		a[i] = 1;
	}
	for(i = 1 ; i < 11 ; ++i){
		for(j = b[i] ; j <= 6000 ; ++j){
			a[j] += a[j - b[i]];
		}
	}

	while(true){
		scanf("%lf",&n);
		if(n == 0.00){
			break;
		}

		int num = (int)(n*20.0);
		printf("%6.2lf%17lld\n",n,a[num]);
	}

	return 0;
}