UVA - 357

 /*
       _________
      /         \
     /  _     _  \
    /   0     0   \
   |       ||     |
   |              | => HI
    \     -----   /
     \           /
      \_ _ _ _ _/
 */

#include<bits/stdc++.h>
using namespace std;
using lli = int64_t;
const int maxN = 30200;
lli grid[5][maxN];
int coins[] = {1,5,10,25,50};
lli solve(int idx,int n){
    if(idx == 5 or n == 0){
        return n == 0;
    }
    if(grid[idx][n] != -1){
        return grid[idx][n];
    }
    lli res = 0;
    for(int i = 0;i <= n; i++){
        if(n - (i * coins[idx]) >= 0){
            res += solve(idx + 1,n - (i * coins[idx]));
        }else{
            break;
        }
    }
    return grid[idx][n] = res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(grid,-1,sizeof(grid));
    int n;
    while(cin >> n and EOF){
        lli res = solve(0,n);
        if(res == 1){
            cout << "There is only 1 way to produce " << n << " cents change.\n";
            continue;
        }
        cout << "There are " << res << " ways to produce " << n << " cents change.\n";
    }
}