Sunday, November 9, 2014

UVa Problem 674 - Coin Change

Problem:

Solution:

The analysis of this problem is identical to my solution of UVa Problem 147 - Dollars. So I don't bother going through it again here.

Only if I knew the two problems (actually the previous one also) is that similar, I wouldn't attempt it, it is a waste of time from a learning perspective.

The only thing I did in this problem is to update the coin set and the I/O routines.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=615

#include "UVa674.h"
#include <iostream>
#include <iomanip>

typedef long long int64;

using namespace std;

const int UVa674_num_values = 5;
int UVa674_values[UVa674_num_values] = {1, 5, 10, 25, 50};
const int UVa674_max_cents = 7489;
// ways[i, j] represents the number of ways i cents can be represented using the first [0, j] values
int64 UVa674_ways[UVa674_max_cents + 1][UVa674_num_values];

int UVa674()
{
for (int j = 0; j < UVa674_num_values; j++)
{
UVa674_ways[0][j] = 1; // There is only one way to represent 0 cents no matter what values are allowed
}

for (int i = 1; i <= UVa674_max_cents; i++)
{
// Step 1: The number of ways to represent i cents in terms of just using a 1 cents is 1.
UVa674_ways[i][0] = 1;

// Step 2: The number of ways to represent i cents in terms of using values[0] .. values[j] is
// Choosing how many instance of of the largest value to use
// and then just sum the rest
for (int j = 1; j < UVa674_num_values; j++)
{
int current = UVa674_values[j];
int64 way = 0;
for (int n = 0; n <= i / current; n++)
{
way += UVa674_ways[i - n * current][j - 1];
}
UVa674_ways[i][j] = way;
}
}

while (!cin.eof())
{
int value;
cin >> value;
if (cin.fail())
{
break;
}
cout << UVa674_ways[value][UVa674_num_values - 1] << endl;
}
return 0;
}