UVA – 357 – Let Me Count The Ways

#include	<stdio.h>
#define FOR(ii, i0, in) for((ii)=(i0); (ii)<(in); ++(ii))
#define FOR2d(ii, jj, i0, j0, in, jn) FOR(ii, i0, in) FOR(jj, j0, jn)
#define MAX 30005
long count[MAX + 2];
long coins[] = { 1, 5, 10, 25, 50 };

int main() {
	int i, j, d;
	count[0] = 1;

	FOR2d(i, j, 0, 0, 5, MAX)
		count[j] += (j - coins[i] >= 0) ? count[j - coins[i]] : 0;

	while (scanf("%d", &d) == 1)
		if(count[d] > 1)
			printf("There are %ld ways to produce %d cents change.\n",  count[d], d);
		else
			printf("There is only 1 way to produce %d cents change.\n", d);
	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: