fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4.  
  5. int dp[10000];
  6. int coins[] = { 50, 20, 10, 5, 1 };
  7. int rec(int n, int cutoff)
  8. {
  9.   if (n == 0) return 1;
  10.   if (dp[n] != -1) return dp[n];
  11.   int cnt = 0;
  12.   for (int i = cutoff; i < 5; i++)
  13.     if (coins[i] <= n) cnt += rec(n - coins[i], i);
  14.   return dp[n] = cnt;
  15. }
  16.  
  17. int main()
  18. {
  19. int n;
  20. while (cin >> n)
  21. {
  22. memset(dp, -1, sizeof dp);
  23. cout << rec(n, 0) << endl;
  24. }
  25. return 0;
  26. }
Success #stdin #stdout 0.02s 2764KB
comments (?)
stdin
copy 
1
4
5
10
13
15
20
stdout
copy 
1
1
2
5
5
10
26
https://ideone.com/9rHCQ
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!