/*
User ID: turing_13
Link : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=102
*/
 
#include <bits/stdc++.h>
 
#define pii pair <int,int>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 200
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define loop(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 1000000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int
 
using namespace std;
 
int values[6]={1,2,4,10,20,40};//Multiply the original value by 20 to convert in integer.
int coins[6],dp[MAX],change[MAX];
double amount;
 
int shop_keeperChange(int v)
{
    for(int i=5;i>-1;i--)
    {
        if(v>=values[i])
            return 1+shop_keeperChange(v-values[i]);
    }
    return 0;
}
 
 
int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
 
    while(cin>>coins[0]>>coins[1]>>coins[2]>>coins[3]>>coins[4]>>coins[5])
    {
        if(!coins[0] && !coins[1] && !coins[2] && !coins[3] && !coins[4] && !coins[5])
            break;
        sc("%lf",&amount);
        ms(dp,inf);
        dp[0]=0;
        for(int c=0;c<6;c++)
        {
            while(coins)
            {
                for(int i=MAX-coins-1;i>-1;i--)
                {
                    if(dp[i]<inf)
                    {
                        dp[i+values]=min(dp[i]+1,dp[i+values]);
                    }
                }
                coins--;
            }
        }
 
        int money=amount*20;
        int ans=inf;
        for(int i=money;i<MAX;i++)
        {
            ans=min(ans,dp[i]+shop_keeperChange(i-money));
        }
        pf("%3d\n",ans);
    }
    return 0;
}

Another solution of the problem is this. But this one slower than upper one. 🙂

#include <bits/stdc++.h>

#define pii pair <int,int>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 200
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define loop(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 1000000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int

using namespace std;

int values[6]={1,2,4,10,20,40};//Multiply the original value by 20 to convert in integer.
int coins[6],dp[MAX],change[MAX];
double amount;

void func()
{
    ms(change,inf);
    change[0]=0;
    for(int c=0;c<6;c++)
    {
        for(int i=0;i<MAX-values-1;i++)
        {
            change[i+values]=min(change[i]+1,change[i+values]);
        }
    }
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    func();
    while(cin>>coins[0]>>coins[1]>>coins[2]>>coins[3]>>coins[4]>>coins[5])
    {
        if(!coins[0] && !coins[1] && !coins[2] && !coins[3] && !coins[4] && !coins[5])
            break;
        sc("%lf",&amount);
        ms(dp,inf);
        dp[0]=0;
        for(int c=0;c<6;c++)
        {
            while(coins)
            {
                for(int i=MAX-coins-1;i>-1;i--)
                {
                    if(dp[i]<inf)
                    {
                        dp[i+values]=min(dp[i]+1,dp[i+values]);
                    }
                }
                coins--;
            }
        }

        int money=amount*20;
        int ans=inf;
        for(int i=money;i<MAX;i++)
        {
            ans=min(ans,dp[i]+shop_keeperChange(i-money));
        }
        pf("%3d\n",ans);
    }
    return 0;
}