UVa - 147 - Dollars

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم  #####*******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define sc(n) scanf("%d", &n)
8. #define S 30003
9. using namespace std;
10. typedef long long LL;
11.  
12. LL N, dp[15][S];
13. LL coins[] = {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};
14. LL Dollars(int ind, LL tot){
15.     if(tot == 0LL)return 1LL;
16.     if(tot < 0)return 0LL;
17.     if(ind >= 11)return 0LL;
18.     if(dp[ind][tot] != -1LL)return dp[ind][tot];
19.     dp[ind][tot] = (Dollars(ind, tot-coins[ind])+Dollars(ind+1, tot));
20.     return dp[ind][tot];
21. }
22.  
23. void Do(){
24.     char n[10];
25.     memset(dp, -1LL, sizeof(dp));
26.     while(scanf("%s", n) == 1){
27.         N = 0LL;
28.         for(int i = 0; n[i]; i++){
29.             if(n[i] >= '0' && n[i] <= '9')
30.                 N = (N*10LL)+(n[i]-'0');
31.         }
32.         if(N == 0LL)break;
33.         printf("%6s%17lld\n", n, Dollars(0, N));
34.     }
35. }
36.  
37. int main(){
38.     ios_base::sync_with_stdio(0); cin.tie(0);
39.     #ifndef ONLINE_JUDGE
40.     ///freopen("inp","r",stdout);
41.     ///freopen("contest.txt","w",stdout);
42.     #endif
43.     Do();
44.     return 0;
45. }