# ZeroJudge - d119: 有獎徵答：換零錢
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=d119
###### tags: `ZeroJudge` `動態規劃（Dynamic Programming）`

#include <iostream>
#include <sstream>
using namespace std;

long long DP[50001] = { 1 };
int changes[10] = { 1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000 };

void Initialize() {
	for (int i = 0; i < 10; ++i)
		for (int j = changes[i]; j <= 50000; ++j)
			DP[j] += DP[j - changes[i]];
}

int main() {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	Initialize();
	int sums, number;
	stringstream ss;
	string way;
	while (getline(cin, way), way != "0") {
		ss.clear(); ss.str(way); sums = 0;
		while (ss >> number)
			sums += number;
		cout << DP[sums] - 1 << '\n';
	}
}