UVa 147 - Dollars

/**
@author - Rumman BUET CSE'15
problem - UVA 147 - Dollars

*/
#include<bits/stdc++.h>
#define ll long long
#define fo freopen("out.txt","w",stdout)
#define fi freopen("in.txt","r",stdin)
#define DEBUG printf("hi\n");
#define DEBUG2 printf("bi\n");
#define pi acos(-1)
//#define m 100000007
#define d 0.000000001

using namespace std ;

ll curr[] = { 2000, 1000, 400, 200, 100 , 40, 20, 10, 4, 2 ,1 }; ;
ll dp[20][1000000] ;

ll rec(ll i , int n)
{
    if(n == 0)
        return 1 ;
    if(n < 0)
        return 0 ;
    if(i > 10 && n > 0)
        return 0 ;

    if(dp[i][n]!=-1)
        return dp[i][n] ;

    return dp[i][n] = rec(i , n - curr[i]) + rec(i+1 , n) ;
}

int main()
{
//    fi ; fo ;
    double m ;
    int mk ;
    memset(dp , -1 , sizeof(dp));

    while(scanf("%lf",&m) && m!=0)
    {

        double k ;
//        k = m*1000 ; ///
        mk = m * 20  ;
//        mk/=10 ;
//        cout << m - mk << " " <<  m << " " <<  mk << endl ;

//printf("%d %f",mk , k);
        ll ans ;
        ans = rec(0 , mk) ;

        if(m < 10)
        {
            printf("  %.2f%17lld\n",m , ans) ;
        }
        else if(m < 100)
        {
            printf(" %.2f%17lld\n",m , ans) ;
        }
        else
        printf("%.2f%17lld\n",m , ans) ;
    }

    return 0 ;
}