UVA Problem 357 – Let Me Count The Ways Solution

UVA Problem 357 – Let Me Count The Ways Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

At first have a look at UVA 674 – Coin Change. Both of these can be solved with dynamic programming and they are almost same with only minor differences. Again we are asked to count the number of ways we can distribute given amount of money with 1, 5, 10, 25, 50 Dollar coins.

One gotcha for this problem is that output is so large int can’t hold that value. Using long or long long can solve this problem. Rest just modify the while loop as the given output format.

Here the first code is almost the same as the coin change problem. In the previous code i split the loops in two ways. But here in the second code I combined all the loops into a single loop. Although this may be slower.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

17 
11
4

Output:

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.

Split Loop Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 357 – Let Me Count The Ways Solution
 */

#include<stdio.h>
#define N 30002

static long long a[N];
static const long long coins[4] = {5, 10, 25, 50};

int main(){
    register unsigned long long i, j;
	long long n;

    for(i = 0; i < N; ++i)
        a[i] = 1;

    for(i = 0; i < 4; ++i){
        for(j = coins[i]; j < N; ++j)
            a[j] += a[j - coins[i]];
    }

	while(scanf("%lld", &n) == 1){
        if(a[n] == 1)
            printf("There is only %lld way to produce %lld cents change.\n", a[n], n);
        else
            printf("There are %lld ways to produce %lld cents change.\n", a[n], n);
    }
	return 0;
}

Combined / Loop Fusion:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 357 – Let Me Count The Ways Solution
 */

#include<stdio.h>
#define N 30002

static long long a[N];
static const unsigned coins[5] = {1, 5, 10, 25, 50};

int main(){
    register unsigned int i, j;
	unsigned n;

    /**
     * This is a bit slower than split loop version
     * In problem 674 i split the loop in two different ways
     * We can apply this for both UVA problem 357 and 674
     */
    a[0] = 1;
    for(i = 0; i < 5; ++i){
        for(j = coins[i]; j < N; ++j)
            a[j] += a[j - coins[i]];
    }

	while(scanf("%lld", &n) == 1){
        if(a[n] == 1)
            printf("There is only %lld way to produce %u cents change.\n", a[n], n);
        else
            printf("There are %lld ways to produce %u cents change.\n", a[n], n);
    }
	return 0;
}
Advertisements