fork download
copy 
  1. #include <stdio.h>
  2.  
  3. 	int ways(int a, int d[], int n)
  4. 	{ 
  5.  
  6. 		int dp[a+1];
  7. 		int i,j;
  8.  
  9. 		for(i=0;i<=a;i++)
  10. 		  dp[i]=0;
  11.  
  12. 		  dp[0]=1;
  13.  
  14.  
  15. 		for(i=0;i<n;i++)
  16. 	      {
  17.  
  18. 	      	for(j=d[i];j<=a;j++)
  19. 	      	{
  20. 	      		dp[j] += dp[j-d[i]];
  21. 	      	}
  22. 	      }
  23. 	      return dp[a];
  24. 	      }
  25.  
  26.  
  27. 	    int main()
  28. 	    {
  29. 	    	 int amount, original, i, count;
  30. 	    	 int d[] = {500,200,100,50,20,10,5,2,1};
  31.  
  32.  
  33. 	    	 scanf("%d", &amount);
  34.  
  35.  
  36. 	    	 original = amount;
  37.  
  38.  
  39. 	    	 for (i = 0; i < 9; i++)
  40. 	    	 {
  41.  
  42.  
  43. 	    	 	count = amount / d[i];
  44. 	    	 	amount = amount % d[i];
  45.  
  46.  
  47. 	    	 	printf("%d : %d\n", d[i], count);
  48.  
  49. 	    	 }
  50.  
  51. 	    	 printf("distinct ways = %d\n", ways(original, d,9));
  52.  
  53.  
  54. 	return 0;
  55. }
  56.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
888
stdout
copy 
500 : 1
200 : 1
100 : 1
50 : 1
20 : 1
10 : 1
5 : 1
2 : 1
1 : 1
distinct ways = 160576583
https://ideone.com/WUCuta
language:
C (gcc 8.3)
created:
3 days 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!