UVa 357 - Let Me Count The Ways

Codes

Wrong way to solve the problem

357-LetMeCountTheWays_wrong.cpp

#include <iostream>
#include <stdint.h>
 
#define CANT_COINS 5
 
using namespace std;
 
uint64_t coins[CANT_COINS] = {1, 5, 10, 25, 50};
 
uint64_t ways(int32_t n, uint32_t max_coin) {
    uint64_t result = 0;
    uint32_t i = 0;
    if (n < 0)
        return 0;
    if (n <= 1)
        return 1;
    for (; i < max_coin; ++i)
        result += ways(n - coins[i], i+1);
 
    return result;
}
 
int main() {
 
    int32_t n;
 
    while (cin >> n) {
        uint64_t res = ways(n, CANT_COINS);
        if (res == 1)
            cout << "There is only 1 way to produce " << n << " cents change.\n";
        else
            cout << "There are " << res << " ways to produce " << n << " cents change.\n";
    }
    return 0;
}

Right way to solve the problem

357-LetMeCountTheWays_right.cpp

#include <iostream>
#include <stdint.h>
 
#define CANT_COINS 5
#define MAX_CENTS 30001
 
using namespace std;
 
uint64_t coins[CANT_COINS] = {50, 25, 10, 5, 1};
uint64_t results[MAX_CENTS] = {0};
 
void init() {
    uint32_t i, j, c;
 
    results[0] = 1;
 
    for(i = 0; i < CANT_COINS; ++i) {
        c = coins[i];
        for (j = c; j < MAX_CENTS; ++j)
            results[j] += results[j-c];
    }
 
}
 
int main() {
    int32_t n;
 
    init();
 
    while (cin >> n) {
        uint64_t res = results[n];
        if (res == 1)
            cout << "There is only 1 way to produce " << n << " cents change.\n";
        else
            cout << "There are " << res << " ways to produce " << n << " cents change.\n";
    }
    return 0;
 
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License