Advertisement
Guest User

Untitled

a guest
Sep 15th, 2012
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.03 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <gmp.h>
  4.  
  5. int main(int argc, char *argv[])
  6. {
  7.     const int denominations[] = { 1, 5, 10, 25, 50, 100, 200, 500, 1000, 2000, 5000, 10000 };
  8.     const int lenDenominations = sizeof(denominations)/sizeof(denominations[0]);
  9.     const int target = 9000000;
  10.  
  11.     MP_INT (*table)[lenDenominations] = malloc(sizeof(MP_INT)*(target+1)*lenDenominations);
  12.     for (int i = 0; i < lenDenominations; i++)
  13.         mpz_init_set_si(&table[target][i], 1);
  14.  
  15.     for (int sumSoFar = target-1; sumSoFar >= 0; sumSoFar--)
  16.     {
  17.         for (int minDenomination = lenDenominations-1; minDenomination >= 0; minDenomination--)
  18.         {
  19.             mpz_init_set_si(&table[sumSoFar][minDenomination], 0);
  20.             for (int i = minDenomination; i < lenDenominations; i++)
  21.             {
  22.                 int newSumSoFar = sumSoFar + denominations[i];
  23.                 if (newSumSoFar <= target)
  24.                     mpz_add(&table[sumSoFar][minDenomination], &table[sumSoFar][minDenomination], &table[newSumSoFar][i]);
  25.             }
  26.         }
  27.     }
  28.  
  29.     mpz_out_str(stdout, 10, &table[0][0]);
  30.     fputc('\n', stdout);
  31.  
  32.     return 0;
  33. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement