Computer Programming Contest Preparation

    1 #include <bits/stdc++.h>
    2 using namespace std;
    3 int main()
    4 {
    5     //pre-calculating every possible amount of money can be given as input
    6     int way[7490];
    7     int coin[5] = {50,25,10,5,1};
    8     memset(way,0,sizeof(way));
    9     way[0]=1; //not taking any coins also an option
   10     for (int j=0; j<5; j++)
   11         {
   12             for (int i=1; i<7490; i++)
   13                 {
   14                     if (i>=coin[j])
   15                         {
   16                             way[i]+=way[i-coin[j]]; // using dynamic approach
   17                         }
   18                 }
   19         }
   20     int n;
   21     scanf("%d",&n);
   22     for (int i=1; i<=n; i++)
   23         {
   24             int d;
   25             scanf("%d",&d);
   26             cout<<way[d]<<endl;
   27         }
   28 
   29 }
   30 
   31