UVA Problem 147 – Dollars Solution

UVA Problem 147 – Dollars Solution:


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

Solving Technique:

This problem is very very very very similar to uva 674 ( Coin Change ) and uva 357 ( Let me count the ways ). These problems can be used as hint or template for this problem. So if you want to solve on your own don’t look down.

In this problem a few key points are,
  1. The amount doesn’t exceed $300.00
  2. Exit / terminate program for the input of 0.00
  3. Amount can be / is a floating point number
  4. There are different values that can be used make up the decimal and the fractional portion
  5. Output should be justified with width 6 before printing input amount and width 17 afterwards then the number of ways the amount is made up of.

Solution Technique:

Instead of calculating the decimal and the fractional portion separately we can use one method to calculate the count. Since a Dollar can be made up of coins that is, $1 = 100 cents. So we can just calculate how many ways the coins can be made and that will be the answer.

For example,
  • $4.70      =      470 cents
  • $2.00      =      200 cents
  • $6.75      =      675 cents
  • $300.00  =  30000 cents

So we can put all the ways the coins can be divided to an array. Then use that calculate the count. Now whenever we can divide the amount with a specific coin we increase the count. We need calculate for all the specific coins.

Here I have given two codes, they are essentially the same. Only difference is in the second code instead of using an array to calculate the count, I have split the loop to show the calculations.

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. Compile with C++ to be safe from compile errors although some codes do work with C compiler.


Input:

0.20
2.00
4.90
6.70
8.45
0.00

 


Output:

  0.20                4
  2.00              293
  4.90             5698
  6.70            19187
  8.45            49007

Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 147 - Dollars
 */

#include<stdio.h>

#define N 30002

static long long c[N];
static const unsigned coins[] = {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};

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

    c[0] = 1;
    for(i = 0; i < 11; ++i){
        for(j = coins[i]; j < N; ++j)
            c[j] += c[j - coins[i]];
    }

	while(scanf("%f", &n) == 1 && n){
        // Rounding error fix
        unsigned coin = (unsigned)((n + 0.001) * 100);

        // 6 width justified including the input amount and 17 width afterwards including count
        printf("%6.2f%17lld\n", n, c[coin]);
    }
	return 0;
}

Code (Loop Split):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 147 - Dollars ( Loop Split )
 */

#include<stdio.h>

#define N 30002

static long long c[N];

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

    c[0] = 1;

    /*
     * Loop Split
     */

    for(j = 5; j < N; ++j)
        c[j] += c[j - 5];

    for(j = 10; j < N; ++j)
        c[j] += c[j - 10];

    for(j = 20; j < N; ++j)
        c[j] += c[j - 20];

    for(j = 50; j < N; ++j)
        c[j] += c[j - 50];

    for(j = 100; j < N; ++j)
        c[j] += c[j - 100];

    for(j = 200; j < N; ++j)
        c[j] += c[j - 200];

    for(j = 500; j < N; ++j)
        c[j] += c[j - 500];

    for(j = 1000; j < N; ++j)
        c[j] += c[j - 1000];

    for(j = 2000; j < N; ++j)
        c[j] += c[j - 2000];

    for(j = 5000; j < N; ++j)
        c[j] += c[j - 5000];

    for(j = 10000; j < N; ++j)
        c[j] += c[j - 10000];

	while(scanf("%f", &n) == 1 && n){
        // Rounding error fix
        unsigned coin = (unsigned)((n + 0.001) * 100);

        // 6 width justified including the input amount and 17 width afterwards including count
        printf("%6.2f%17lld\n", n, c[coin]);
    }
	return 0;
}
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s