## 147 - Dollars

Moderator: Board moderators

Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm
Ok, i've replaced (int)(amount * 100 + 0.5) with (int)(amount * 20 + 0.5) and modified the array, and got AC...

Could someone explain why (int)(amount * 100) doesn't work (i've done some debugging and found out that, for example, when amount is 0.06, amount * 100 casted to int is 5 !?!)

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
This is due to floating point precision error. For example, 0.5 in base 10 (decimal) is the same as 0.1 in base 2(binary)

So 0.06 in base 10 is the same as 0.0000111101... in base 2. THe floating point precision error is due to the fact that numbers are represented in binary and calculations invovling the numbers are done in binary. Hope this explanation is clear enough.

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am
I use DP algorithm and got AC in 0.03 sec.

if you want to use double or float make sure you + 0.5 before change it to int

because precision of binary machine code

i didn't use double or float

[cpp] while (scanf("%d.%c%c", &input, &d1, &d2) == 3)[/cpp]

just input the char

hope it will help

good luck

Andrew Neitsch
New poster
Posts: 43
Joined: Fri Jun 25, 2004 9:37 pm
The lround() function will round a float to the nearest integer.

NAME
lround, lroundf, lroundl, llround, llroundf, llroundl - round to near-
est integer, away from zero

SYNOPSIS
#include <math.h>

long int lround(double x);
long int lroundf(float x);
long int lroundl(long double x);

long long int llround(double x);
long long int llroundf(float x);
long long int llroundl(long double x);

DESCRIPTION
These functions round their argument to the nearest integer value,
rounding away from zero, regardless of the current rounding direction.
If x is infinite or NaN, or if the rounded value is outside the range
of the return type, the numeric result is unspecified. A domain error
may occur if the magnitude of x is too large.

RETURN VALUE
The rounded integer value.

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
I think there is something I don't understand about printf formatting. The following 147 solution of mine got AC but with a presentation error. May someone please guide me as to how I'm supposed to properly format the answer? I've tried googling the subject, but haven't managed to find anything useful. Below is the code I submitted to get an AC with presentation error:

[c] [/c]

Thanks.
Last edited by Minilek on Tue Aug 03, 2004 7:39 am, edited 1 time in total.

Andrew Neitsch
New poster
Posts: 43
Joined: Fri Jun 25, 2004 9:37 pm
printf("%6.2f ...

I use an old MSDN CD for my C library reference. The newer versions aren't nearly as good, but they're online at msdn.microsoft.com. Look for the 'library' link.

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
Thanks! AC.
Last edited by Minilek on Tue Aug 03, 2004 7:39 am, edited 1 time in total.

Andrew Neitsch
New poster
Posts: 43
Joined: Fri Jun 25, 2004 9:37 pm
Posting AC code on the board is generally frowned upon.

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

### 147 why CE!

here is my code.anyone tell me why compile error?

//code start
#include <stdio.h>

#define max 30100

long long coin[]={5,10,20,50,100,200,500,1000,2000,5000,10000};
double input,copy;
long long matrix[max],i,j;

void main(){
for(i=0;i<11;i++)matrix=1;
for(i=5;i<max;i+=5)matrix=1;
for(i=1;i<11;i++)
for(j=5;j<max;j+=5){
if(j>=coin)
matrix[j]=matrix[i-1][j]+matrix[ j-coin ];
else
matrix[j]=matrix[i-1][j];
}
while(scanf("%lf",&input)==1){
if(!input)break;
copy=100.*input;
printf("%.2lf %lld\n",input,matrix[copy]);
}
}
khobaib

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
You can't index a table with doubles.

New poster
Posts: 8
Joined: Fri Sep 24, 2004 8:40 am

### help with 147!

hi
Plz tell me what is the logic that is wrong orwhat cases am i missing for the prob 147 ,here is my code: Code: Select all

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

int a[]={10000,5000,2000,1000,500,200,100,50,20,10,5};

int dollars(int i,int n)
{
int chng=0;
if(i<11&&n>0)
{
if(n%a[i]==0)
{
chng=chng+dollars(i,n-a[i]);
if(n!=a[i]) chng=chng+dollars(i+1,n-a[i]);
}
if(n%a[i]!=0)
{
int j=1;
while(j*a[i]<n)
{
int k=i+1;
while(k<11)
{
chng=chng+dollars(k,n-j*a[i]);
k++;
}
j++;
}
}
// cout<<"c "<<chng<<endl;
return chng;
}
else if(i==11||n<0) return 0;
else if(n==0) return 1;
}

int main()
{
int ways=0;
int i=0;
double n1;
int n;
cin>>n1;
n1=n1*100+.5;
n=(int)n1;
for(i=0;i<11;i++)
{
if(a[i]<=n)
{
ways=ways+ dollars(i,n);
//cout<<"w "<<ways<<endl;
//cout<<ways<<endl;
//return 0;
}

}
cout<<ways<<endl;
return 0;
}

``````

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
Your program processes only one set of data.
It should continue to take input until 0.00 is entered.
Besides, the outpurt formatting isn't exactly correct. Look at the sample output.

New poster
Posts: 8
Joined: Fri Sep 24, 2004 8:40 am
thankx a lot,but my question was about the logic that i am using in the function dollars.I am not convinced that i am handling all the possible cases ,for eg. take input as .5 and just manually go thru it ,if u can find the missing link that would be great.

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Contact:

Finally I got Accepted
Last edited by TISARKER on Sat Dec 18, 2004 4:48 pm, edited 1 time in total.
Mr. Arithmetic logic Unit

sklitzz
New poster
Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm

### 147 Dollars TLE

Why do I get TLE?!

Code: Select all

``````#include <cstdio>
using namespace std;

const int M = 11, MAX_N = 300 * 100;
int coins[] = { 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000 };

int solve( int N )
{
int dp[MAX_N] = { 0 };
dp = 1;

for( int j = 0; j < M; ++j )
for( int i = 1; i <= N; ++i )
if( i >= coins[j] )
dp[i] += dp[i - coins[j]];

return dp[N];
}

int main()
{
double d;
scanf( "%lf", &d );
while( 	d != 0.0 )
{
printf( "%.2lf %d\n", d, solve( (int)(d * 100) ) );
scanf( "%lf", &d );
}
return 0;
}
``````