fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4. #include <stdint.h>
  5. #include <inttypes.h>
  6.  
  7. #include <sys/time.h>
  8. uint64_t GetTickCount(void)
  9. {
  10.     struct timeval time;
  11.     struct timezone zone;
  12.     gettimeofday(&time, &zone);
  13.     return (uint64_t)time.tv_sec*1000000LL + (uint64_t)time.tv_usec;
  14. }
  15.  
  16.  
  17. #define MAX_AMOUNT_LIST 200000
  18. #define KIND_OF_COIN    6
  19.  
  20. typedef struct Coin {
  21.     int  amount;
  22.     int  coinNum[KIND_OF_COIN];
  23. } Coin;
  24.  
  25. typedef struct CoinStats {
  26.     int    coinWorth[KIND_OF_COIN];
  27.     int    coinWeight[KIND_OF_COIN];
  28.     int    coinNum[KIND_OF_COIN];
  29.     int    coinTypeNum;
  30. } CoinStats;
  31.  
  32. // initialize coin stats (global)
  33. static CoinStats cs = {{   1,   5,  10,  50, 100, 500},
  34.                        {  10,  37,  45,  40,  48,  70},
  35.                        {   0,   0,   0,   0,   0,   0},
  36.                         KIND_OF_COIN};
  37.  
  38. void Sort(Coin *amountList, int amountNum)
  39. {
  40.     int  i, j;
  41.     Coin tmp;
  42.  
  43.     // sort by amount (bubble sort)
  44.     for (i = 0; i < amountNum - 1; i++) {
  45.         for (j = 0; j < amountNum - 1 - i; j++) {
  46.             if (amountList[j].amount > amountList[j+1].amount) {
  47.                 tmp = amountList[j];
  48.                 amountList[j] = amountList[j+1];
  49.                 amountList[j+1] = tmp;
  50.             }
  51.         }
  52.     }
  53. }
  54.  
  55. void CheckWeight(int depth, int remain, Coin *amountList, int *amountNum)
  56. {
  57.     int    i;
  58.     int    nextRemain;
  59.  
  60.     while (remain >= cs.coinWeight[depth] * cs.coinNum[depth]) {
  61.         nextRemain = remain - cs.coinNum[depth] * cs.coinWeight[depth];
  62.         if (depth == KIND_OF_COIN - 1) {
  63.             // if exact weight then add current stats to amountList
  64.             if (remain == (cs.coinNum[depth] * cs.coinWeight[depth])) {
  65.                 if (*amountNum < MAX_AMOUNT_LIST) {
  66.                     amountList[*amountNum].amount = 0;
  67.                     for (i = 0; i < cs.coinTypeNum; i++) {
  68.                         amountList[*amountNum].amount += cs.coinWorth[i] * cs.coinNum[i];
  69.                         amountList[*amountNum].coinNum[i] = cs.coinNum[i];
  70.                     }
  71.                     (*amountNum)++;
  72.                 } else {
  73.                      printf("List Buffer Overflow !\n");
  74.                 }
  75.             }
  76.             cs.coinNum[depth]++;
  77.         } else {
  78.             cs.coinNum[depth + 1] = 0;
  79.             CheckWeight(depth + 1, nextRemain, amountList, amountNum);
  80.             cs.coinNum[depth]++;
  81.         }
  82.     }
  83. }
  84.  
  85. int main(void)
  86. {
  87.     char   strbuf[256];
  88.     int    i;
  89.     int    weight;
  90.     uint64_t t;
  91.  
  92.     Coin   amountList[MAX_AMOUNT_LIST];  // result buffer
  93.     int    amountNum = 0;                // number of result
  94.  
  95.     printf("Weight of Coins (gram) : ");
  96.     fgets(strbuf, sizeof(strbuf), stdin);
  97.     weight = round(atof(strbuf) * 10);
  98.  
  99.     t = GetTickCount();
  100.  
  101.     cs.coinNum[0] = 0;
  102.     CheckWeight(0, weight, amountList, &amountNum);
  103.  
  104.     t = GetTickCount() - t;
  105.  
  106.     // Sort(amountList, amountNum);
  107.  
  108.     printf("\nCoin Weight    : %.1f g\n", (double)weight / 10);
  109.     if (amountNum == 0) {
  110.         printf("No combination found. (may be FAKE !)\n");
  111.     } else {
  112.         printf("Number of List : %d\n", amountNum);
  113.         printf("Time = %"PRId64" us (micro second)\n", t);
  114.         /*
  115.         printf("amount(yen) :   1yen   5yen  10yen  50yen 100yen 500yen\n");
  116.         printf("---------------------------------------------------------\n");
  117.         for (i = 0; i < amountNum; i++) {
  118.             printf(" %10d : %6d %6d %6d %6d %6d %6d\n", amountList[i].amount, 
  119.                         amountList[i].coinNum[0], amountList[i].coinNum[1],
  120.                         amountList[i].coinNum[2], amountList[i].coinNum[3],
  121.                         amountList[i].coinNum[4], amountList[i].coinNum[5]);
  122.         }
  123.         */
  124.     }
  125.     return 0;
  126. }
  127.  
Success #stdin #stdout 0.41s 7404KB
comments (?)
stdin
copy 
200
stdout
copy 
Weight of Coins (gram) : 
Coin Weight    : 200.0 g
Number of List : 163831
Time = 412577 us (micro second)
https://ideone.com/tA1zvD
language:
C (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!