GastonFontenla

UVa; 357 - Let Me Count The Ways

May 29th, 2016
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.70 KB | None | 0 0
  1. #include <stdio.h>
  2.  
  3. int main()
  4. {
  5.     int a[5] = {1, 5, 10, 25, 50};
  6.     long long m[5][30001];
  7.     int n, i, j;
  8.  
  9.     for(i=0; i<5; i++)
  10.         m[i][0] = 1;
  11.     for(i=0; i<30001; i++)
  12.         m[0][i] = 1;
  13.  
  14.     for(i=1; i<5; i++)
  15.     {
  16.         for(j=1; j<30001; j++)
  17.         {
  18.             if(j >= a[i])
  19.                 m[i][j] = m[i-1][j] + m[i][j-a[i]];
  20.             else
  21.                 m[i][j] = m[i-1][j];
  22.         }
  23.     }
  24.  
  25.     while(scanf("%d\n", &n) == 1)
  26.     {
  27.         if(m[4][n] == 1)
  28.             printf("There is only 1 way to produce %d cents change.\n", n);
  29.         else
  30.             printf("There are %lld ways to produce %d cents change.\n", m[4][n], n);
  31.     }
  32.  
  33.     return 0;
  34. }
Advertisement
Add Comment
Please, Sign In to add comment