runtah

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]=;
 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;
}

Go to link download