UVa 357 - Let Me Count The Ways

// UVa 357 - Let Me Count The Ways

#include <iostream>
#include <string.h>
using namespace std;

unsigned long long T[30001][5];
int coin[5] = { 1, 5, 10, 25, 50 };

int main() {
	memset(T, 0, sizeof(T));
	for (int i = 0; i <= 30000; i++) {
		T[i][0] = 1;
		for (int j = 1; j < 5; j++) {
			T[i][j] = T[i][j - 1];
			if (i >= coin[j])
				T[i][j] += T[i - coin[j]][j];
		}
	}
	int n;
	while (cin >> n) {
		unsigned long long m = T[n][4];
		if (m == 1)
			cout << "There is only 1 way";
		else
			cout << "There are " << m << " ways";
		cout << " to produce " << n << " cents change." << endl;
	}
	return 0;
}