#include <stdio.h>
#include <stdlib.h>
#define MAX_AMOUNT_LIST 8192
#define KIND_OF_COIN 6
typedef struct Coin {
int amount;
int coinNum[KIND_OF_COIN];
} Coin;
typedef struct CoinStats {
int coinWorth[KIND_OF_COIN];
double 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},
{ 1.0, 3.7, 4.5, 4.0, 4.8, 7.0},
{ 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, double remain, Coin *amountList, int *amountNum)
{
int i;
double 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;
double weight;
Coin amountList[MAX_AMOUNT_LIST]; // result buffer
int amountNum = 0; // number of result
printf("Weight of Coins (gram) : "); fgets(strbuf
, sizeof(strbuf
), stdin
);
cs.coinNum[0] = 0;
CheckWeight(0, weight, amountList, &amountNum);
Sort(amountList, amountNum);
printf("\nCoin Weight : %.1f g\n", weight
); if (amountNum == 0) {
printf("No combination found. (may be FAKE !)\n"); } else {
printf("Number of List : %d\n", amountNum
); 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;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCiNkZWZpbmUgTUFYX0FNT1VOVF9MSVNUIDgxOTIKI2RlZmluZSBLSU5EX09GX0NPSU4gICAgNgoKdHlwZWRlZiBzdHJ1Y3QgQ29pbiB7CiAgICBpbnQgIGFtb3VudDsKICAgIGludCAgY29pbk51bVtLSU5EX09GX0NPSU5dOwp9IENvaW47Cgp0eXBlZGVmIHN0cnVjdCBDb2luU3RhdHMgewogICAgaW50ICAgIGNvaW5Xb3J0aFtLSU5EX09GX0NPSU5dOwogICAgZG91YmxlIGNvaW5XZWlnaHRbS0lORF9PRl9DT0lOXTsKICAgIGludCAgICBjb2luTnVtW0tJTkRfT0ZfQ09JTl07CiAgICBpbnQgICAgY29pblR5cGVOdW07Cn0gQ29pblN0YXRzOwoKLy8gaW5pdGlhbGl6ZSBjb2luIHN0YXRzIChnbG9iYWwpCnN0YXRpYyBDb2luU3RhdHMgY3MgPSB7eyAgIDEsICAgNSwgIDEwLCAgNTAsIDEwMCwgNTAwfSwKICAgICAgICAgICAgICAgICAgICAgICB7IDEuMCwgMy43LCA0LjUsIDQuMCwgNC44LCA3LjB9LAogICAgICAgICAgICAgICAgICAgICAgIHsgICAwLCAgIDAsICAgMCwgICAwLCAgIDAsICAgMH0sCiAgICAgICAgICAgICAgICAgICAgICAgIEtJTkRfT0ZfQ09JTn07Cgp2b2lkIFNvcnQoQ29pbiAqYW1vdW50TGlzdCwgaW50IGFtb3VudE51bSkKewogICAgaW50ICBpLCBqOwogICAgQ29pbiB0bXA7CiAgICAKICAgIC8vIHNvcnQgYnkgYW1vdW50IChidWJibGUgc29ydCkKICAgIGZvciAoaSA9IDA7IGkgPCBhbW91bnROdW0gLSAxOyBpKyspIHsKICAgICAgICBmb3IgKGogPSAwOyBqIDwgYW1vdW50TnVtIC0gMSAtIGk7IGorKykgewogICAgICAgICAgICBpZiAoYW1vdW50TGlzdFtqXS5hbW91bnQgPiBhbW91bnRMaXN0W2orMV0uYW1vdW50KSB7CiAgICAgICAgICAgICAgICB0bXAgPSBhbW91bnRMaXN0W2pdOwogICAgICAgICAgICAgICAgYW1vdW50TGlzdFtqXSA9IGFtb3VudExpc3RbaisxXTsKICAgICAgICAgICAgICAgIGFtb3VudExpc3RbaisxXSA9IHRtcDsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KfQoKdm9pZCBDaGVja1dlaWdodChpbnQgZGVwdGgsIGRvdWJsZSByZW1haW4sIENvaW4gKmFtb3VudExpc3QsIGludCAqYW1vdW50TnVtKQp7CiAgICBpbnQgICAgaTsKICAgIGRvdWJsZSBuZXh0UmVtYWluOwogICAgCiAgICB3aGlsZSAocmVtYWluID49IGNzLmNvaW5XZWlnaHRbZGVwdGhdICogY3MuY29pbk51bVtkZXB0aF0pIHsKICAgICAgICBuZXh0UmVtYWluID0gcmVtYWluIC0gY3MuY29pbk51bVtkZXB0aF0gKiBjcy5jb2luV2VpZ2h0W2RlcHRoXTsKICAgICAgICBpZiAoZGVwdGggPT0gS0lORF9PRl9DT0lOIC0gMSkgewogICAgICAgICAgICAvLyBpZiBleGFjdCB3ZWlnaHQgdGhlbiBhZGQgY3VycmVudCBzdGF0cyB0byBhbW91bnRMaXN0CiAgICAgICAgICAgIGlmIChyZW1haW4gPT0gKGNzLmNvaW5OdW1bZGVwdGhdICogY3MuY29pbldlaWdodFtkZXB0aF0pKSB7CiAgICAgICAgICAgICAgICBpZiAoKmFtb3VudE51bSA8IE1BWF9BTU9VTlRfTElTVCkgewogICAgICAgICAgICAgICAgICAgIGFtb3VudExpc3RbKmFtb3VudE51bV0uYW1vdW50ID0gMDsKICAgICAgICAgICAgICAgICAgICBmb3IgKGkgPSAwOyBpIDwgY3MuY29pblR5cGVOdW07IGkrKykgewogICAgICAgICAgICAgICAgICAgICAgICBhbW91bnRMaXN0WyphbW91bnROdW1dLmFtb3VudCArPSBjcy5jb2luV29ydGhbaV0gKiBjcy5jb2luTnVtW2ldOwogICAgICAgICAgICAgICAgICAgICAgICBhbW91bnRMaXN0WyphbW91bnROdW1dLmNvaW5OdW1baV0gPSBjcy5jb2luTnVtW2ldOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAoKmFtb3VudE51bSkrKzsKICAgICAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICAgICAgIHByaW50ZigiTGlzdCBCdWZmZXIgT3ZlcmZsb3cgIVxuIik7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICAgICAgY3MuY29pbk51bVtkZXB0aF0rKzsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICBjcy5jb2luTnVtW2RlcHRoICsgMV0gPSAwOwogICAgICAgICAgICBDaGVja1dlaWdodChkZXB0aCArIDEsIG5leHRSZW1haW4sIGFtb3VudExpc3QsIGFtb3VudE51bSk7CiAgICAgICAgICAgIGNzLmNvaW5OdW1bZGVwdGhdKys7CiAgICAgICAgfQogICAgfQp9CgppbnQgbWFpbih2b2lkKQp7CiAgICBjaGFyICAgc3RyYnVmWzI1Nl07CiAgICBpbnQgICAgaTsKICAgIGRvdWJsZSB3ZWlnaHQ7CiAgICAKICAgIENvaW4gICBhbW91bnRMaXN0W01BWF9BTU9VTlRfTElTVF07ICAvLyByZXN1bHQgYnVmZmVyCiAgICBpbnQgICAgYW1vdW50TnVtID0gMDsgICAgICAgICAgICAgICAgLy8gbnVtYmVyIG9mIHJlc3VsdAogICAgCiAgICBwcmludGYoIldlaWdodCBvZiBDb2lucyAoZ3JhbSkgOiAiKTsKICAgIGZnZXRzKHN0cmJ1Ziwgc2l6ZW9mKHN0cmJ1ZiksIHN0ZGluKTsKICAgIHdlaWdodCA9IGF0b2Yoc3RyYnVmKTsKICAgIAogICAgY3MuY29pbk51bVswXSA9IDA7CiAgICBDaGVja1dlaWdodCgwLCB3ZWlnaHQsIGFtb3VudExpc3QsICZhbW91bnROdW0pOwogICAgU29ydChhbW91bnRMaXN0LCBhbW91bnROdW0pOwogICAgCiAgICBwcmludGYoIlxuQ29pbiBXZWlnaHQgICAgOiAlLjFmIGdcbiIsIHdlaWdodCk7CiAgICBpZiAoYW1vdW50TnVtID09IDApIHsKICAgICAgICBwcmludGYoIk5vIGNvbWJpbmF0aW9uIGZvdW5kLiAobWF5IGJlIEZBS0UgISlcbiIpOwogICAgfSBlbHNlIHsKICAgICAgICBwcmludGYoIk51bWJlciBvZiBMaXN0IDogJWRcbiIsIGFtb3VudE51bSk7CiAgICAgICAgcHJpbnRmKCJhbW91bnQoeWVuKSA6ICAgMXllbiAgIDV5ZW4gIDEweWVuICA1MHllbiAxMDB5ZW4gNTAweWVuXG4iKTsKICAgICAgICBwcmludGYoIi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLVxuIik7CiAgICAgICAgZm9yIChpID0gMDsgaSA8IGFtb3VudE51bTsgaSsrKSB7CiAgICAgICAgICAgIHByaW50ZigiICUxMGQgOiAlNmQgJTZkICU2ZCAlNmQgJTZkICU2ZFxuIiwgYW1vdW50TGlzdFtpXS5hbW91bnQsIAogICAgICAgICAgICAgICAgICAgICAgICBhbW91bnRMaXN0W2ldLmNvaW5OdW1bMF0sIGFtb3VudExpc3RbaV0uY29pbk51bVsxXSwKICAgICAgICAgICAgICAgICAgICAgICAgYW1vdW50TGlzdFtpXS5jb2luTnVtWzJdLCBhbW91bnRMaXN0W2ldLmNvaW5OdW1bM10sCiAgICAgICAgICAgICAgICAgICAgICAgIGFtb3VudExpc3RbaV0uY29pbk51bVs0XSwgYW1vdW50TGlzdFtpXS5jb2luTnVtWzVdKTsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gMDsKfQo=