UVa/674(CoinChange)

// UVa/674: Coin Change

#include<bits/stdc++.h>
using namespace std;
#define LL long long

LL values[] = { 50, 25, 10, 5, 1 };
LL n = 5;

LL coinChange(LL amount)
{
    LL dp[n+1][amount+1];

    for(LL i=0; i<=n; i++) dp[i][0] = 1;

    for(LL j=1; j<=amount; j++) dp[0][j] = 0;

    for(LL i=1; i<=n; i++){
        for(LL j=1; j<=amount; j++){
            if(values[i-1] <= j)
                dp[i][j] = dp[i-1][j] + dp[i][j - values[i-1]];
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    return dp[n][amount];
}

int main()
{
    LL amount;
    while(scanf("%lld", &amount) == 1) {
        LL solution = coinChange(amount);
        printf("%lld\n", solution);
    }
    return 0;
}