#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdint.h>
#include <inttypes.h>

#include <sys/time.h>
uint64_t GetTickCount(void)
{
    struct timeval time;
    struct timezone zone;
    gettimeofday(&time, &zone);
    return (uint64_t)time.tv_sec*1000000LL + (uint64_t)time.tv_usec;
}


#define MAX_AMOUNT_LIST 200000
#define KIND_OF_COIN    6

typedef struct Coin {
    int  amount;
    int  coinNum[KIND_OF_COIN];
} Coin;

typedef struct CoinStats {
    int    coinWorth[KIND_OF_COIN];
    int    coinWeight[KIND_OF_COIN];
    int    coinNum[KIND_OF_COIN];
    int    coinTypeNum;
} CoinStats;

// initialize coin stats (global)
static CoinStats cs = {{   1,   5,  10,  50, 100, 500},
                       {  10,  37,  45,  40,  48,  70},
                       {   0,   0,   0,   0,   0,   0},
                        KIND_OF_COIN};

void Sort(Coin *amountList, int amountNum)
{
    int  i, j;
    Coin tmp;
    
    // sort by amount (bubble sort)
    for (i = 0; i < amountNum - 1; i++) {
        for (j = 0; j < amountNum - 1 - i; j++) {
            if (amountList[j].amount > amountList[j+1].amount) {
                tmp = amountList[j];
                amountList[j] = amountList[j+1];
                amountList[j+1] = tmp;
            }
        }
    }
}

void CheckWeight(int depth, int remain, Coin *amountList, int *amountNum)
{
    int    i;
    int    nextRemain;
    
    while (remain >= cs.coinWeight[depth] * cs.coinNum[depth]) {
        nextRemain = remain - cs.coinNum[depth] * cs.coinWeight[depth];
        if (depth == KIND_OF_COIN - 1) {
            // if exact weight then add current stats to amountList
            if (remain == (cs.coinNum[depth] * cs.coinWeight[depth])) {
                if (*amountNum < MAX_AMOUNT_LIST) {
                    amountList[*amountNum].amount = 0;
                    for (i = 0; i < cs.coinTypeNum; i++) {
                        amountList[*amountNum].amount += cs.coinWorth[i] * cs.coinNum[i];
                        amountList[*amountNum].coinNum[i] = cs.coinNum[i];
                    }
                    (*amountNum)++;
                } else {
                     printf("List Buffer Overflow !\n");
                }
            }
            cs.coinNum[depth]++;
        } else {
            cs.coinNum[depth + 1] = 0;
            CheckWeight(depth + 1, nextRemain, amountList, amountNum);
            cs.coinNum[depth]++;
        }
    }
}

int main(void)
{
    char   strbuf[256];
    int    i;
    int    weight;
    uint64_t t;
    
    Coin   amountList[MAX_AMOUNT_LIST];  // result buffer
    int    amountNum = 0;                // number of result
    
    printf("Weight of Coins (gram) : ");
    fgets(strbuf, sizeof(strbuf), stdin);
    weight = round(atof(strbuf) * 10);
    
    t = GetTickCount();
    
    cs.coinNum[0] = 0;
    CheckWeight(0, weight, amountList, &amountNum);
    
    t = GetTickCount() - t;
    
    // Sort(amountList, amountNum);
    
    printf("\nCoin Weight    : %.1f g\n", (double)weight / 10);
    if (amountNum == 0) {
        printf("No combination found. (may be FAKE !)\n");
    } else {
        printf("Number of List : %d\n", amountNum);
        printf("Time = %"PRId64" us (micro second)\n", t);
        /*
        printf("amount(yen) :   1yen   5yen  10yen  50yen 100yen 500yen\n");
        printf("---------------------------------------------------------\n");
        for (i = 0; i < amountNum; i++) {
            printf(" %10d : %6d %6d %6d %6d %6d %6d\n", amountList[i].amount, 
                        amountList[i].coinNum[0], amountList[i].coinNum[1],
                        amountList[i].coinNum[2], amountList[i].coinNum[3],
                        amountList[i].coinNum[4], amountList[i].coinNum[5]);
        }
        */
    }
    return 0;
}