Facebook
From Greedy, 4 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 282
  1. #include<stdio.h>
  2. #include<algorithm>
  3.  
  4. using namespace std;
  5.  
  6. int main(){
  7.  
  8.     int coin[100], output[1000],value, coins_no, t_coin=0, change;
  9.     scanf("%d", & coins_no);
  10.  
  11.     for(int i=0;i<coins_no;i++)
  12.         scanf("%d",&coin[i]);
  13.  
  14.     sort(coin,coin+coins_no);
  15.  
  16.     scanf("%d",&value);
  17.  
  18.     int j=0;
  19.     for(int i = coins_no-1; i>=0; i--)
  20.     {
  21.         if(value>0)
  22.         {
  23.             change = value / coin[i];
  24.             t_coin += change;
  25.             value  = value% coin[i];
  26.  
  27.             for(int k = 0;k<change;k++)
  28.             {
  29.                 output[j++] = coin[i];
  30.             }
  31.         }
  32.         else
  33.         {
  34.             break;
  35.         }
  36.     }
  37.     if(value == 0)
  38.     {
  39.         printf("total coins needed = %dnnCoins are:n",t_coin);
  40.         for(int i = 0; i < j; i++)
  41.             printf("t%dn",output[i]);
  42.         printf("n");
  43.  
  44.     }
  45.     else{
  46.         printf("Sorry. No change is availablen");
  47.     }
  48.  
  49. }
  50.