## 147 - Dollars

Moderator: Board moderators

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

### Re: 147 - Dollars

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

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

### Re: 147 Dollars WA

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

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

### Re: why wa 147

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?

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

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 147 - Dollars

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

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

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

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.