Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

Dollars

147.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

double ways[30001][11];

double
calc_ways(int a, int max_currency)
{
	double result=0;

	if (ways[a][max_currency]!=-1) {
		return ways[a][max_currency];
	}
	if (a==0) {
		return 1;
	}
	if (a >= 10000 && max_currency<1) {
		result += calc_ways(a-10000,0);
	}
	if (a >= 5000 && max_currency<2) {
		result += calc_ways(a-5000,1);
	}
	if (a >= 2000 && max_currency<3) {
		result += calc_ways(a-2000,2);
	}
	if (a >= 1000 && max_currency<4) {
		result += calc_ways(a-1000,3);
	}
	if (a >= 500 && max_currency<5) {
		result += calc_ways(a-500,4);
	}
	if (a >= 200 && max_currency<6) {
		result += calc_ways(a-200,5);
	}
	if (a >= 100 && max_currency<7) {
		result += calc_ways(a-100,6);
	}
	if (a >= 50 && max_currency<8) {
		result += calc_ways(a-50,7);
	}
	if (a >= 20 && max_currency<9) {
		result += calc_ways(a-20,8);
	}
	if (a >= 10 && max_currency<10) {
		result += calc_ways(a-10,9);
	}
	if (a >= 5 && max_currency<11) {
		result += calc_ways(a-5,10);
	}
	ways[a][max_currency] = result;
#if DEBUG
	printf("calc_ways(%d,%d)=%d\n", a, max_currency, ways[a][max_currency]);
#endif
	return result;
}

int
main(void)
{
	int i,j;
	int a,b;

	for(i=0; i<=30000; i++) {
		for(j=0; j<11; j++) {
			ways[i][j]=-1;
		}
	}

	while(1) {
		if (scanf("%d.%d", &a, &b)!=2) {
			abort();
		}
		if (a > 300 || b % 5) {
			abort();
		}
		if (a==0 && b==0) {
			break;
		}

		printf("%3d.%02d%17.0f\n", a, b, calc_ways(100*a+b,0));
	}
	exit(0);
}