#include #include using namespace std; int values[] = { 1, 5, 10, 25 }; /* int ways(int amount, int last_usable) { if (amount == 0) return 1; // the result is the empty set of coins, that's still a valid solution if (last_usable < 0) return 0; if (amount < values[last_usable]) // can't use that coin at all, it is too big return ways(amount, last_usable - 1); int n1 = ways(amount - values[last_usable], last_usable); int n2 = ways(amount, last_usable - 1); return n1 + n2; } */ int main(int argc, char * argv[]) { int answers[10000][4]; for (int c = 0; c < 4; c += 1) answers[0][c] = 1; for (int r = 0; r < 10000; r += 1) answers[r][0] = 1; for (int r = 1; r < 10000; r += 1) for (int c = 1; c < 4; c += 1) if (r >= values[c]) answers[r][c] = answers[r - values[c]][c] + answers[r][c - 1]; else answers[r][c] = answers[r][c - 1]; cout << answers[atoi(argv[1])][3] << "\n"; }