[UVa] 147 - Dollars

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;

typedef long long ll;


ll table[30000][100];

ll change(ll n, ll m, int *S)
{

    if (n==0) return 1;
    else if (n<0) return 0;
    else if (m<0 && n>=1) return 0;

    //cout << n << " -- " << table[n][m]<< endl;
    //getchar();

    if (table[n][m]!=-1) return table[n][m];

    return (table[n][m] = change(n,m-1,S)+change(n-S[m],m,S));
}

ll parse(string n)
{
    int len = n.length(), i, j;
    char stor[100];
    for (i=0, j=0 ; i<len ; i++)
    {
        if (n[i]>='0' && n[i]<='9')
            stor[j++]=n[i];
    }
    stor[j]='\0';
    return (ll)atol(stor);
}


int main()
{
    int i, j;
    ll n, m, val;
    string inp;

    int S[100];

    for (i=0 ; i<=30000 ; i++)
    {
        for (j=0 ; j<=20 ; j++)
        {
            table[i][j]=-1;
        }
    }

    S[0] = 5;
    S[1] = 10;
    S[2] = 20;
    S[3] = 50;
    S[4] = 100;
    S[5] = 200;
    S[6] = 500;
    S[7] = 1000;
    S[8] = 2000;
    S[9] = 5000;
    S[10] = 10000;

    for (i=0 ; i<=30000 ; i++)
    {
        for (j=0 ; j<=20 ; j++)
        {
            table[i][j]=-1;
        }
    }

    while (cin >> inp)
    {
        if (inp=="0.00") break;

        n = parse(inp);
        val = change(n,10,S);
        cout.width(6);
        cout << inp;
        cout.width(17);
        cout << val << endl;
    }
    return 0;
}