# UVa 562 – Dividing coins

0

## Solution Idea:

In this problem given n coins where value of every coin is <=500. We have to divide this coins into two parts so that the difference between the sum of the values of coins  in each parts is minimum.

To do this at first wile taking input we sum up all the coins value. and we can see that the maximum sum can be  50000 and if we divide it into two parts then one part can have maximum of 25000 sum. So we take a dp array size greater than 25000 and run coin change to make values from coins. after that we have to check which largest value we can make from the coins which is less than or equal to sum/2. where sum is the summation of all coins value.

Let the largest value we can make is X. so our output is (sum-X)-X  or sum-2*x.

```
/*
+-+ +-+ +-+
|R| |.| |S|
+-+ +-+ +-+
*/

#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 db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI              vector &lt;int&gt;
#define DBG             pf(&quot;Hi\n&quot;)
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)          scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)        scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)       scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)     scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)    scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define loop(i,n)       for(int i=0;i&lt;n;i++)
#define REP(i,a,b)      for(int i=a;i&lt;b;i++)
#define TEST_CASE(t)    for(int z=1;z&lt;=t;z++)
#define PRINT_CASE      printf(&quot;Case %d: &quot;,z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

bool dp[30000];
int coins[200];

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

int t,n;
sf(t);
TEST_CASE(t)
{
int n,sum=0;
sf(n);
loop(i,n) sf(coins[i]),sum+=coins[i];

ms(dp,false);

int mid=(sum/2);

dp[0]=1;

loop(i,n)
{
for(int j=mid; j-coins[i]&gt;=0; j--)
dp[j] |=dp[j-coins[i]];

}

for(int i=sum/2; i&gt;=0; i--)
if(dp[i])
{
printf(&quot;%d\n&quot;,abs((sum-i)-i));
break;
}

}

return 0;
}

```

# UVa 1213 – Sum of Different Primes

0

## Solution Idea:

This problem is similar to Uva 10616 – Divisible Group Sums . This one can be solved using knapsack or Coin change. In this problem the objects or coins are prime numbers. So at first we calculate the prime numbers using sieve algorithm in the given range of input.

Then we simply call a dp function and show the ans. In this problem the value of objects or coins is not changing in every cases so we need not to clear the dp array every time. We just calculate the process backwards in dp function.

```
/*
+-+ +-+ +-+
|R| |.| |S|
+-+ +-+ +-+
*/

#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 db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI              vector &lt;int&gt;
#define DBG             pf(&quot;Hi\n&quot;)
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)          scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)        scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)       scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)     scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)    scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define loop(i,n)       for(int i=0;i&lt;n;i++)
#define REP(i,a,b)      for(int i=a;i&lt;b;i++)
#define TEST_CASE(t)    for(int z=1;z&lt;=t;z++)
#define PRINT_CASE      printf(&quot;Case %d: &quot;,z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

vector&lt;int&gt; prime;
bool visit[1130];
int n,k;

void sieve()
{
for(int i=2;i&lt;1130;)
{
prime.pb(i);
for(int j=i+i;j&lt;1130;j+=i)
visit[j]=1;
for(++i;;i++) if(visit[i]==0) break;
}
}

ll dp[195][15][1130];

ll func(int idx, int cnt, int sum)
{
if(cnt==0)
{
if(sum==0) return 1;
return 0;
}

if(idx&gt;=SZ(prime)) return 0;

ll &amp;ret=dp[idx][cnt][sum];

if(ret!=-1) return ret;

int p=0,q=0;

if(sum-prime[idx]&gt;=0) p=func(idx+1,cnt-1,sum-prime[idx]);
q=func(idx+1,cnt,sum);

return ret=p+q;
}

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

sieve();

ms(dp,-1);

while(sff(n,k)==2 &amp;&amp; (n &amp;&amp; k))
{
ll ans=func(0,k,n);
pf(&quot;%lld\n&quot;,ans);
}

return 0;
}

```

# UVa 10664 – Luggage

0

## Solution Idea:

The main problem is an array of integers is given and we have to divide the array into two small array in such a way so that the sum of both arrays are same.

At first we take input and sum up the array values. if the total sum is odd then it’s confirm that we can’t split it into two equal sum. so that we can output “NO”.

If the sum is Even then we can use knapsack of Coin Change any algorithm to check if we can make the (sum/2) value from the given array values. Here I am using knapsack.

As the input of this problem is tricky because we don’t know how many numbers there will be in a line. So for this problem I use stringstream to solve this problem.

```
/*
+-+ +-+ +-+
|R| |.| |S|
+-+ +-+ +-+
*/

#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 db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI              vector &lt;int&gt;
#define DBG             pf(&quot;Hi\n&quot;)
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)          scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)        scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)       scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)     scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)    scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define loop(i,n)       for(int i=0;i&lt;n;i++)
#define REP(i,a,b)      for(int i=a;i&lt;b;i++)
#define TEST_CASE(t)    for(int z=1;z&lt;=t;z++)
#define PRINT_CASE      printf(&quot;Case %d: &quot;,z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

vector&lt;int&gt; v;

int dp[30][110];

int knapsack(int idx, int val)
{
if(val==0) return 1;
if(idx==SZ(v)) return 0;

int &amp;ret=dp[idx][val];
if(ret!=-1) return ret;

int p=0,q=0;

if(val-v[idx]&gt;=0) p=knapsack(idx+1,val-v[idx]);
q=knapsack(idx+1,val);

return ret=p|q;

}

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

int m;
cin&gt;&gt;m;
getchar();
while(m--)
{
string str;
getline(cin,str);
stringstream ss;
ss&lt;&lt;str;
int val;
int sum=0;
while(ss&gt;&gt;val)
{
v.pb(val);
sum+=val;
}

if(sum &amp; 1)
cout&lt;&lt;&quot;NO&quot;&lt;&lt;endl;
else
{
ms(dp,-1);
if(knapsack(0,sum/2))
cout&lt;&lt;&quot;YES&quot;&lt;&lt;endl;
else
cout&lt;&lt;&quot;NO&quot;&lt;&lt;endl;
}

v.clear();

}

return 0;
}

```

# UVa 357 – Let Me Count The Ways

0

## Solution Idea:

This problem is same as UVa 11137 – Ingenuous Cubrency . In this problem just the value of coins are changed and rest of the things is similar. you can see solution idea from that problem and can solve that one as well 😀 .

```
/*
+-+ +-+ +-+
|R| |.| |S|
+-+ +-+ +-+
*/

#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 db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI              vector &lt;int&gt;
#define DBG             pf(&quot;Hi\n&quot;)
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)          scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)        scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)       scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)     scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)    scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define loop(i,n)       for(int i=0;i&lt;n;i++)
#define REP(i,a,b)      for(int i=a;i&lt;b;i++)
#define TEST_CASE(t)    for(int z=1;z&lt;=t;z++)
#define PRINT_CASE      printf(&quot;Case %d: &quot;,z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

int coins[6]={1,5,10,25,50};

ll dp[30100];

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

dp[0]=1;

loop(i,5)
{
REP(j,coins[i],30100)
{
dp[j]+=dp[j-coins[i]];
}
}

int n;

while(sf(n)==1)
{
if(dp[n]&gt;1)
pf(&quot;There are %lld ways to produce %d cents change.\n&quot;,dp[n],n);
else
pf(&quot;There is only 1 way to produce %d cents change.\n&quot;,n);
}

return 0;
}

```

# UVa 11137 – Ingenuous Cubrency

1

## Solution Idea:

This is a classical coin change  problem and this can be solved using dp. Here the coins  value are the cubic value of 1 to 21. we take a array called dp[] which size is greater than the maximum amount of input value. At first dp array contains only 0. Now we set dp[0]=1 because we can make 0 in 1 way and that is 0 😛 .

Now we run a loop via i and j for all index where i control coins value and j controls dp array index and calculate this…

dp[j]+=dp[j-coins[i]]

After this iteration we just take input and print the value of the dp array at that input index.

```
/*
+-+ +-+ +-+
|R| |.| |S|
+-+ +-+ +-+
*/

#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 db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI              vector &lt;int&gt;
#define DBG             pf(&quot;Hi\n&quot;)
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)          scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)        scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)       scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)     scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)    scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define loop(i,n)       for(int i=0;i&lt;n;i++)
#define REP(i,a,b)      for(int i=a;i&lt;b;i++)
#define TEST_CASE(t)    for(int z=1;z&lt;=t;z++)
#define PRINT_CASE      printf(&quot;Case %d: &quot;,z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

ll dp[10100];
int coins[30];

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

REP(i,1,22) coins[i]=sqr(i)*i;

dp[0]=1;

for(int i=1;i&lt;22;i++)
{
for(int j=coins[i];j&lt;10100;j++)
if(dp[j-coins[i]])
dp[j]+=dp[j-coins[i]];
}

int n;

while(sf(n)==1)
{
pf(&quot;%lld\n&quot;,dp[n]);
}

return 0;
}

```

# UVa 674 – Coin Change

0

## IDEA:

• This is the straight forward coin change algorithm. this can be done both recursively and iteratively.
• dp array store the result which calculate the coinchange() function.
```
/*
+-+ +-+ +-+
|R| |.| |S|
+-+ +-+ +-+
*/

#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 db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI              vector &lt;int&gt;
#define DBG             pf(&quot;Hi\n&quot;)
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)          scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)        scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)       scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)     scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)    scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define loop(i,n)       for(int i=0;i&lt;n;i++)
#define REP(i,a,b)      for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;b;i--)
#define TEST_CASE(t)    for(int z=1;z&lt;=t;z++)
#define PRINT_CASE      printf(&quot;Case %d: &quot;,z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

int coin[10]= {1,5,10,25,50};

ll dp[10500];

void coinchange()
{
dp[0]=1;
loop(i,5)
{
REP(j,coin[i],9999)
{
dp[j]+=dp[j-coin[i]];
}
}
}

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

coinchange();
int n;
while(sf(n)==1)
{
pf(&quot;%lld\n&quot;,dp[n]);
}
return 0;
}

```

# Light OJ 1233 – Coin Change (III)

0

```
/*
+-+ +-+ +-+
|R| |.| |S|
+-+ +-+ +-+
*/

#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 db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI              vector &lt;int&gt;
#define DBG             pf(&quot;Hi\n&quot;)
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf(&quot;%d&quot;,&amp;a)
#define sff(a,b)        scanf(&quot;%d%d&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)     scanf(&quot;%d%d%d&quot;,&amp;a,&amp;b,&amp;c)
#define loop(i,n)       for(int i=0;i&lt;n;i++)
#define REP(i,a,b)      for(int i=a;i&lt;b;i++)
#define TEST_CASE(t)    for(int z=1;z&lt;=t;z++)
#define PRINT_CASE      printf(&quot;Case %d: &quot;,z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

/*----------------------- Graph Moves---------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*--------------------------------------------------------------*/

int Set(int N,int pos)
{
return N=N | (1&lt;&lt;pos);
}
int reset(int N,int pos)
{
return N= N &amp; ~(1&lt;&lt;pos);
}
bool check(int N,int pos)
{
return (bool)(N &amp; (1&lt;&lt;pos));
}
/*--------------------------------------------------------------*/

bool dp[100005];
int num_coin[100005];
int n,m;
int coin[110],num[110];
int main()
{
///freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
///freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);
int t;
sf(t);
TEST_CASE(t)
{
sff(n,m);
loop(i,n)
{
sf(coin[i]);
}
loop(i,n)
{
sf(num[i]);
}
loop(i,m+2)
{
dp[i]=0;
num_coin[i]=inf;
}
dp[0]=1;
num_coin[0]=0;
int cnt=0;
for(int i=0; i&lt;n; i++)
{
int val=coin[i];
int hi=0;
int temp=val;
for(int k=val; k&lt;=m; k++)
{
if(dp[k]==0 &amp;&amp; dp[k-val]==1 &amp;&amp; num_coin[k-val]+1&lt;=num[i])
{
dp[k]=1;
if(dp[k])
cnt++;
num_coin[k]=num_coin[k-val]+1;
}
}
loop(j,m+2) num_coin[j]=0;
num_coin[0]=0;
}
PRINT_CASE;
pf(&quot;%d\n&quot;,cnt);
}
return 0;
}

```

# UVa 11517 – Exact Change

0

Idea:
1. This is a classical coin change problem. here dp array represent the minimum coin need to make an amount. example – dp[100] means we need at least dp[100] coins to make 100 cents.

2. At first calculate the dp[] table as described. then start a linear search from money to forward for finding first amount of money which value is not infinity as we set before dp calculation and when we find a such value that value is the payable money and dp value of that money is the minimum number of coins.

```
/*
MMP&quot;&quot;MM&quot;&quot;YMM   db      `7MN.   `7MF'`7MMM.     ,MMF' .g8&quot;&quot;8q.`YMM'   `MM'
P'   MM   `7  ;MM:       MMN.    M    MMMb    dPMM .dP'    `YM.VMA   ,V
MM      ,V^MM.      M YMb   M    M YM   ,M MM dM'      `MM VMA ,V
MM     ,M  `MM      M  `MN. M    M  Mb  M' MM MM        MM  VMMP
MM     AbmmmqMA     M   `MM.M    M  YM.P'  MM MM.      ,MP   MM
MM    A'     VML    M     YMM    M  `YM'   MM `Mb.    ,dP'   MM
.JMML..AMA.   .AMMA..JML.    YM  .JML. `'  .JMML. `&quot;bmmd&quot;'   .JMML.
*/

#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 10000
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a) (int)a.size()
#define si(a) scanf(&quot;%d&quot;,&amp;a)
#define sii(a,b) scanf(&quot;%d%d&quot;,&amp;a,&amp;b)
#define siii(a,b,c) scanf(&quot;%d%d%d&quot;,&amp;a,&amp;b,&amp;c)
#define loop(i,n) for(int i=0;i&lt;n;i++)
#define REP(i,a,b) for(int i=a;i&lt;b;i++)
#define TEST_CASE(t) for(int z=1;z&lt;=t;z++)
#define PRINT_CASE printf(&quot;Case %d: &quot;,z)
#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 dp[20100];

int coin[110];

int main()
{
///freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
///freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);
int t;
si(t);
TEST_CASE(t)
{
int money;
si(money);
int n;
si(n);
loop(i,n)
{
si(coin[i]);
}
//sort(coin,coin+n,test);
ms(dp,inf);
dp[0]=0;
for(int i=0; i&lt;n; i++)
{
for(int j=money; j&gt;-1; j--)
{
dp[j+coin[i]]=min(dp[j]+1,dp[j+coin[i]]);
}
}

for(int i=money; i&lt;=30100; i++)
{
if(dp[i]&lt;10000)
{
pf(&quot;%d %d\n&quot;,i,dp[i]);
break;
}
}
}
return 0;
}

```

Another Solution using same idea. this one is from revise 😛 .

```

/*
+-+ +-+ +-+
|R| |.| |S|
+-+ +-+ +-+
*/

#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 db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI              vector &lt;int&gt;
#define DBG             pf(&quot;Hi\n&quot;)
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)          scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)        scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)       scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)     scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)    scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define loop(i,n)       for(int i=0;i&lt;n;i++)
#define REP(i,a,b)      for(int i=a;i&lt;b;i++)
#define TEST_CASE(t)    for(int z=1;z&lt;=t;z++)
#define PRINT_CASE      printf(&quot;Case %d: &quot;,z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define ull             unsigned long long

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

int dp[1000007];
int coin[110];

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

int t;
sf(t);
TEST_CASE(t)
{
ms(dp,1000000);
int money,n;
sf(money);
sf(n);
loop(i,n) sf(coin[i]);
dp[0]=0;
for(int i=0; i&lt;n; i++)
{
for(int j=money; j&gt;=0; j--)
{
dp[j+coin[i]]=min(dp[j]+1,dp[j+coin[i]]);
}
}

for(int i=money;; i++)
{
if(dp[i]&lt;1000000 &amp;&amp; dp[i])
{
pf(&quot;%d %d\n&quot;,i,dp[i]);
break;
}
}

}

return 0;
}

```

# UVa 166 – Making Change

0
```
/*
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;
}

```

# UVa 147 – Dollars

0

This one is very tricky input problem. If u take input in a float then somehow convert it in int then the original value doesn’t exist.
For Example:
if we write:
double a = 1.15;
int x=floor(a);
int b=(a-x)*100;
then the value of b is 14 😀 .
Because 1.15 exist in double a like 1.149999999999999999.

So this process is not capable to solve the problem.

```
/*
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 30500
#define SZ(a) (int)a.size()
#define getint(a) scanf(&quot;%d&quot;,&amp;a)
#define loop(i,a) for(int i=0;i&lt;a;i++)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int

using namespace std;

int coins[11]= {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000 };
unsigned long long dp[30500];

int main()
{
///freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
///freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);
int a,b;
dp[0]=1;
for(int i=0;i&lt;11;i++)
for(int j=coins[i];j&lt;MAX;j++)
dp[j]+=dp[j-coins[i]];
while(sc(&quot;%d.%d&quot;,&amp;a,&amp;b))
{
int amount=a*100+b;
if(amount==0)
break;
pf(&quot;%3d.%d%d%17llu\n&quot;,a,b/10,b%10,dp[amount]);
}
return 0;
}

```