# ZeroJudge - d133: 00357 - Let Me Count The Ways
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=d133
###### tags: `ZeroJudge` `動態規劃（Dynamic Programming）`

#include <iostream>
using namespace std;

long long ways[30001] = { 1 };

void Initialize() {
	int changes[5] = { 1, 5, 10, 25, 50 };
	for (int i = 0; i < 5; ++i)
		for (int j = changes[i]; j <= 30000; ++j)
			ways[j] += ways[j - changes[i]];
}

int main() {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	Initialize();
	int money;
	while (cin >> money)
		if (ways[money] == 1)
			cout << "There is only 1 way to produce " << money << " cents change.\n";
		else
			cout << "There are " << ways[money] << " ways to produce " << money << " cents change.\n";
}