#include #include #include const std::array coins = {1, 2, 5, 10, 20, 50, 100, 200}; std::map, int> solved; int ways(int C, int max = 7); int ways(int C, int max) { int ret = 0; // Only one way to make 1p or 0p if (C == 1 || max == 0) { return ( 1 ); } else if (C == 0) { return ( 1 ); } else if (max == 1) { // Only using 1p and 2p, there are floor(n/2)+1 combinations. return ( (C >> 1) + 1 ); } // Check already calculated values auto search = solved.find({C, max}); if (search != solved.end()) { return search->second; } // Cannot use coins higher than value. int i = max; while (coins[i] > C) { --i; } // Use all smaller denominations. for (; i >= 0; --i) { ret += ways(C - coins[i], i); } // Add to known solutions. solved[{C, max}] = ret; // If max is greater than the amount, then smaller // larger denominations also have the same combinations. // (e.g. C=20p, max=200p is the same as C=20p, max=100p) while (coins[--max] > C) { solved[{C, max}] = ret; } return ret; } int main(int argc, char const *argv[]) { int x; std::cin >> x; std::cout << ways(x) << std::endl; return 0; }