fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define Speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  3. #define ll long long
  4. #define ld long double
  5. #define all(name) name.begin(),name.end()
  6. #define rall(name) name.rbegin(),name.rend()
  7. #define vin(S,E,N) for(int i=S;i<E;i++)cin>>N[i];
  8. #define S second
  9. #define F first
  10. #define endl "\n"
  11. #define PI acos(-1)
  12. #define YES cout << "YES\n"
  13. #define NO cout << "NO\n"
  14. #define int ll
  15. using namespace std;
  16. const int N = 1e4+5;
  17. void fropen() {
  18.     freopen("circles.in", "r", stdin);
  19.     freopen("angle2.out", "w", stdout);
  20. }
  21. int n ;
  22. vector<int> v(N,0);
  23. int mem[5][30005],coins[]={1,5,10,25,50};
  24. int rec(int i , int remaining){
  25.     if (remaining == 0) return 1;
  26.     if (i==5 || coins[i] > remaining) return 0;
  27.     int &ans = mem[i][remaining];
  28.     if (~ans) return ans;
  29.     ans = rec(i+1,remaining);
  30.     if (coins[i]<=remaining)
  31.         ans += rec(i,remaining-coins[i]);
  32.     return ans;
  33. }
  34. void solution() {
  35.     memset(mem,-1,sizeof(mem));
  36.     while (cin >> n){
  37.         int ans = rec(0, n);
  38.         if (ans == 1)
  39.             cout << "There is only 1 way to produce " << n << " cents change.\n";
  40.         else
  41.             cout << "There are " << ans << " ways to produce " << n << " cents change.\n";
  42.     }
  43. }
  44. signed main(){
  45.     //fropen();
  46.     Speed;
  47.     int t = 1;
  48.     //cin >> t;
  49.     for (int i=1 ; i<=t ; i++) {
  50.         solution();
  51.     }
  52. }
  53.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
17
11
4
stdout
copy 
There are 6 ways to produce 17 cents change.
There are 4 ways to produce 11 cents change.
There is only 1 way to produce 4 cents change.
https://ideone.com/gRKUH0
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

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!