Advertisement
Farjana_akter

Untitled

Jul 28th, 2019
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.83 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long int dp[8][30005]={0};
  4.  
  5. int main()
  6. {
  7. freopen("in.txt","r",stdin);
  8. freopen("out.txt","w",stdout);
  9. int num=5;
  10. int coin[num+5];
  11. long long int n,i,j,k,ans;
  12. coin[1]=1;
  13. coin[2]=5;
  14. coin[3]=10;
  15. coin[4]=25;
  16. coin[5]=50;
  17. for(i=1;i<=num;i++)
  18. dp[i][0]=1;
  19. while(cin>>n)
  20. {
  21. for(i=1;i<=num;i++)
  22. {
  23. for(j=1;j<=n;j++)
  24. {
  25. if(j<coin[i])
  26. dp[i][j]=dp[i-1][j];
  27. else
  28. dp[i][j]=dp[i-1][j]+dp[i][j-coin[i]];
  29. }
  30. }
  31. ans=dp[5][n];
  32. if(ans==1)
  33. cout<<"There is only "<<1<<" way to produce "<<n<<" cents change."<<endl;
  34. else
  35. cout<<"There are "<<ans<<" ways to produce "<<n<<" cents change."<<endl;
  36.  
  37. }
  38. return 0;
  39. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement