OJ Board

Code: Select all

# include <stdio.h>
# include <stdlib.h>
# include <iostream>
using namespace std;

int main ()
{
	int uang;
	long long dp[5][30001];
	int nilai[5] = {1,5,10,25,50};
		
	for (int i = 0; i <= uang; i++)
	{
		dp[0][i] = 1;
	}
		
	for (int i = 1; i < 5; i++)
	{
		for (int j = 0; j <= 30000; j++)
		{
			if (j < nilai[i]) dp[i][j] = dp[i-1][j];
			else
			{
				dp[i][j] = dp[i-1][j] + dp[i][j-nilai[i]];
			}
		}
	}
	
	while (scanf("%d", &uang) == 1)
	{
		if (dp[4][uang] > 1)
		{
			cout << "There are " << dp[4][uang] << " ways to produce " << uang << " cents change.\n";
		}
		else
		{
			cout << "There is only 1 way to produce " << uang << " cents change.\n";
		}
	}
}