UVa : 147 (Dollars)



// http://uva.onlinejudge.org/external/1/147.html

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <sstream>
#include <set>
#include <cmath>
#define N 1000000
using namespace std;

int main ()
{
    int coins [] = {1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000};
    double dp [6000 + 10];

    memset (dp, 0, sizeof (dp));

    dp [0] = 1;

    for ( int i = 0; i < 11; i++ ) {
        for ( int j = 1; j <= 6000; j++ ) {
            if ( j - coins [i] >= 0 )
                dp [j] += dp [j - coins [i]];
        }
    }

    double c;

    while ( scanf ("%lf", &c) ) {
        if ( c == 0 ) break;
        int index = c * 20;

        printf ("%6.2lf%17.lf\n", c, dp [index]);
    }

    return 0;
}

// @END_OF_SOURCE_CODE

3 thoughts on “UVa : 147 (Dollars)

  1. @Aslan Naurzbai
    for the ease of calculation.
    Let me explain, the lowest amount is 5c .. so we need to multiply all the numbers by 20 to make the lowest coin a full number 1
    in this way, we will be able to work with only integers and no fraction part will bother us

  2. from your above dp program , below is the the recursion formula , but it also counts the subsets which are same in value but order is different. how the above program is taking care of that :
    int f2(int S , vector sol)
    {
    if(S == 0) { return 1;} /*does make a solution*/
    if(S < 0) return 0; /*does not make a solution*/

    int count =0;
    /* try out each option from V */
    for(int i=0; i< 3 ;i++){
    count += f2(S – V[i]);
    }
    return count;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s