147 - Dollars

[Tomislav Novak]

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]

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]

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]

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]

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.

[Andrew Neitsch]

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]

Thanks! AC.

[Andrew Neitsch]

Posting AC code on the board is generally frowned upon.

[lovemagic]

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[11][max],i,j;

void main(){
for(i=0;i<11;i++)matrix[0]=1;
for(i=5;i<max;i+=5)matrix[0]=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[10][copy]);
}
}

[Krzysztof Duleba]

You can't index a table with doubles.

[vladimir manich]

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]

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.

[vladimir manich]

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]

Finally I got Accepted

[sklitzz]

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[0] = 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;
}