Page 6 of 16

Posted: Thu Jun 03, 2004 8:25 pm
by 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 !?!)

Posted: Sat Jun 05, 2004 12:01 pm
by 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.

Posted: Sat Jul 24, 2004 9:14 am
by 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

Posted: Tue Jul 27, 2004 6:08 pm
by 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.

Posted: Mon Aug 02, 2004 11:13 am
by 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]
:D
[/c]

Thanks.

Posted: Mon Aug 02, 2004 6:47 pm
by 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.

Posted: Tue Aug 03, 2004 3:08 am
by Minilek
Thanks! AC.

Posted: Tue Aug 03, 2004 4:58 am
by Andrew Neitsch
Posting AC code on the board is generally frowned upon.

147 why CE!

Posted: Sat Sep 18, 2004 11:27 am
by 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]);
}
}

Posted: Sat Sep 18, 2004 10:06 pm
by Krzysztof Duleba
You can't index a table with doubles.

help with 147!

Posted: Sun Sep 26, 2004 6:33 am
by 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;
}


Posted: Sun Sep 26, 2004 7:34 am
by 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.

Posted: Sun Sep 26, 2004 9:13 am
by 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.

Dollars(147) Why Wrong answer??????

Posted: Tue Nov 09, 2004 12:09 pm
by TISARKER
Finally I got Accepted

147 Dollars TLE

Posted: Mon Feb 14, 2005 11:12 pm
by 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;
}