# UVa 166 – Making Change

```
/*
User ID: turing_13
*/

#include &lt;bits/stdc++.h&gt;

#define pii pair &lt;int,int&gt;
#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&lt;&lt;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(&quot;%d&quot;,&amp;a)
#define loop(i,n) for(int i=0;i&lt;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&gt;-1;i--)
{
if(v&gt;=values[i])
return 1+shop_keeperChange(v-values[i]);
}
return 0;
}

int main()
{
///freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
///freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

while(cin&gt;&gt;coins[0]&gt;&gt;coins[1]&gt;&gt;coins[2]&gt;&gt;coins[3]&gt;&gt;coins[4]&gt;&gt;coins[5])
{
if(!coins[0] &amp;&amp; !coins[1] &amp;&amp; !coins[2] &amp;&amp; !coins[3] &amp;&amp; !coins[4] &amp;&amp; !coins[5])
break;
sc(&quot;%lf&quot;,&amp;amount);
ms(dp,inf);
dp[0]=0;
for(int c=0;c&lt;6;c++)
{
while(coins)
{
for(int i=MAX-coins-1;i&gt;-1;i--)
{
if(dp[i]&lt;inf)
{
dp[i+values]=min(dp[i]+1,dp[i+values]);
}
}
coins--;
}
}

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

```

Another solution of the problem is this. But this one slower than upper one. ðŸ™‚

```

#include &lt;bits/stdc++.h&gt;

#define pii pair &lt;int,int&gt;
#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&lt;&lt;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(&quot;%d&quot;,&amp;a)
#define loop(i,n) for(int i=0;i&lt;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&lt;6;c++)
{
for(int i=0;i&lt;MAX-values-1;i++)
{
change[i+values]=min(change[i]+1,change[i+values]);
}
}
}

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

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

```