147 - Dollars

[lighted]

Change float to double. Also add epsilon value here.

Code: Select all

cout<<right<<table[(int)(n + 1e-8)]<<endl;

I never use float, i always use double.

[yishiliu666]

Hi everyone, could you please help me check why this code gets WA, I am fairly sure it's correct since I compared my result with result from UVa toolkit and they are the same.

Code: Select all

#include<iostream>
#include<cstdio>

using namespace std;
int const N = 6001;
long long dp[N][11];
const int values[] = {1,2,4,10,20, 40, 100,200,400,1000,2000};

long long fill(int val, int last){
	if(last < 0){
		return 0;
	}
	
	if(dp[val][last] != 0){
		return dp[val][last];
	}
	
	if(val >= values[last]){
		dp[val][last] = fill(val - values[last], last) + fill(val, last-1);
	}else{
		dp[val][last] = fill(val, last-1);
	}
	return dp[val][last];

}

int main(){
	float amount;
	for(int i=0; i<9; i++){
		dp[0][i] = 1;
	}
	
	do{
		cin >> amount;
		if(amount == 0)
			break;
		long long num = fill(amount*100/5, 10);
		printf("%6.2f%17lld\n", amount, num);
	}while(1);

}

Here're my testcases I checked on UVa toolkit

299.50
0.05
300.00
0.30
0.50
1.05
2.35
10.05
234.75
299.00
199.00
145.35
149.80

and output

299.50 179049898891112
0.05 1
300.00 181490736388615
0.30 6
0.50 13
1.05 50
2.35 442
10.05 104561
234.75 25587526467069
299.00 176638443641346
199.00 7123659819223
145.35 677284457250
149.80 846861153162

[lighted]

Try to use search (147) and post in existing thread. Don't open new thread.

Problem is precision errors. I always use double instead of float. Change your code

Code: Select all

double amount;
..
long long num = fill (amount * 100 / 5 + 1e-8, 10);
printf ("%6.2lf%17lld\n", amount, num);

Don't forget to remove your code after getting accepted.

[Zyaad Jaunnoo]

In short, to illustrate what it is, consider the following C/C++ boolean expressions:

Code: Select all

(int)(0.29 * 100) == 28
(int)(0.57 * 100) == 56
(int)(0.58 * 100) == 57
(int)(1.13 * 100) == 112
(int)(1.14 * 100) == 113
(int)(1.15 * 100) == 114
...

Here's the bummer: they all evaluate to true. You didn't see that coming, did you?

I suggest you read this article and this paper if you're curious why.

Thanks a lot for guiding!

On the other hand, I used sprintf and sscanf to extract the whole and decimal parts.

Code: Select all

while (scanf("%lf", &amount) && amount > 0) 
{
	sprintf(input, "%.2lf", amount);
	sscanf(input, "%d.%d", &whole, &decimal);
	printf("%6.2lf%17lld\n", amount, nways(whole * 100 + decimal, 10));
}

[Tanmoy Tapos Datta]

I have checked all kinds of input and in every output is correct. But getting WA . What's the reason of WA . Some one please help me...

Code: Select all

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <sstream>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <string>
#include <map>

#define pii pair <int,int>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 30500
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define loop(i,a) for(int i=0;i<a;i++)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int

using namespace std;

int coins[11]= {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000 };
unsigned long long dp[30500];

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    double a;
    dp[0]=1;
    for(int i=0;i<11;i++)
        for(int j=coins[i];j<MAX;j++)
            dp[j]+=dp[j-coins[i]];
    while(sc("%lf",&a))
    {
        int x,y;
        x=floor(a);
        y=(a-(double)x)*100;
        int amount=x*100+y;
        if(amount==0)
            break;
        pf("%6.2lf%17llu\n",a,dp[amount]);
    }
    return 0;
}

[brianfry713]

1.15 62

[Ovro]

Getting TLE. I am using recursion here. Should that cause any problem?

Code: Select all

#include<iostream>
#include<iomanip>
using namespace std;

unsigned long long int ara[11][30010];
int coin[] = {10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5};
unsigned long long coinChange(int type, int value)
{
    if(type == 11 || value < 0)
        return 0;
    else if(value == 0)
        return ara[type][value] = 1;

    if(ara[type][value] != 0)
        return ara[type][value];

    return ara[type][value] = coinChange(type+1, value) + coinChange(type, value - coin[type]);
}

int main()
{
    float fAmount;
    int iAmount;
    unsigned long long ans;

    while(cin >> fAmount)
    {
        if(fAmount == 0.00)
            break;

        iAmount = fAmount * 100;

        ans = coinChange(0, iAmount);
        cout << setw(6) << fixed << setprecision(2) << fAmount << setw(17) << ans << "\n";
    }
    return 0;
}

[Ovro]

Now i am having a peculiar problem. I edited my code and this time i got WA. I can see that, for input 1.15 my code outputs 0 in codeblocks. But in visual studio 2012 the same code outputs 62. Why are there two different outputs for same input and for same code ? I am using default settings in both codeblocks and visual studio.
Any help guys?

Code: Select all

#include<iostream>
#include<iomanip>
#include<cstring>
using namespace std;

unsigned long long int ara[11][30010];
int coin[] = {10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5};
unsigned long long coinChange(int type, int value)
{
    if(type == 11 || value < 0)
        return 0;
    else if(value == 0)
        return ara[type][value] = 1;

    if(ara[type][value] != -1)
        return ara[type][value];

    return ara[type][value] = coinChange(type+1, value) + coinChange(type, value - coin[type]);
}

int main()
{
    float fAmount;
    int iAmount;
    unsigned long long ans;

    memset(ara, -1, sizeof (ara));

    while(cin >> fAmount)
    {
        if(fAmount == 0)
            break;

        iAmount = fAmount * 100;

        ans = coinChange(0, iAmount);
        cout << setw(6) << fixed << setprecision(2) << fAmount << setw(17) << ans << "\n";
    }
    return 0;
}

[aybek]

Guys, I need help. My ideal code is getting WA .

For test case:

Code: Select all

300.00
0.00

It gives:

Code: Select all

300.00   23123301210317

But AC answer (got from uDebug):

Code: Select all

300.00  181490736388615

I checked

Code: Select all

181490736388615 < 2^64-1

Here it is:

Code: Select all

Deleted (Because of AC)

Updated:
Fixed error, all problem was in convertion from float to integer.