147 - Dollars

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 147 - Dollars

Post by lighted » Fri Aug 15, 2014 11:08 pm

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.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

yishiliu666
New poster
Posts: 4
Joined: Tue Mar 11, 2014 2:25 pm

147 Dollars WA

Post by yishiliu666 » Mon Oct 20, 2014 1:52 am

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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 147 Dollars WA

Post by lighted » Mon Oct 20, 2014 3:05 pm

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. 8)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Zyaad Jaunnoo
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

Re: why wa 147

Post by Zyaad Jaunnoo » Mon Dec 29, 2014 2:32 am

mf wrote:
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
New poster
Posts: 5
Joined: Mon Jul 14, 2014 10:04 pm

Re: 147 - Dollars

Post by Tanmoy Tapos Datta » Wed Jan 21, 2015 2:55 am

I have checked all kinds of input and in every output is correct. But getting WA :oops: . 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 147 - Dollars

Post by brianfry713 » Wed Jan 21, 2015 11:05 pm

1.15 62
Check input and AC output for thousands of problems on uDebug!

Ovro
New poster
Posts: 12
Joined: Mon Nov 11, 2013 8:30 am

Re: 147 - Dollars

Post by Ovro » Thu Apr 16, 2015 2:37 pm

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
New poster
Posts: 12
Joined: Mon Nov 11, 2013 8:30 am

Re: 147 - Dollars

Post by Ovro » Fri Apr 17, 2015 9:44 am

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
New poster
Posts: 19
Joined: Fri Jul 19, 2013 10:25 am
Contact:

Re: 147 - Dollars

Post by aybek » Sun Oct 11, 2015 7:36 am

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

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.

Post Reply

Return to “Volume 1 (100-199)”