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

Post Reply
User avatar
Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm

Post by Tomislav Novak » Thu Jun 03, 2004 8:25 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

Post by chunyi81 » Sat Jun 05, 2004 12:01 pm

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

Post by jackie » Sat Jul 24, 2004 9:14 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

Post by Andrew Neitsch » Tue Jul 27, 2004 6:08 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:

Post by Minilek » Mon Aug 02, 2004 11:13 am

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.
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

Post by Andrew Neitsch » Mon Aug 02, 2004 6:47 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:

Post by Minilek » Tue Aug 03, 2004 3:08 am

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

Post by Andrew Neitsch » Tue Aug 03, 2004 4:58 am

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!

Post by lovemagic » Sat Sep 18, 2004 11:27 am

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]);
}
}
khobaib

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sat Sep 18, 2004 10:06 pm

You can't index a table with doubles.

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

help with 147!

Post by vladimir manich » Sun Sep 26, 2004 6:33 am

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;
}


User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sun Sep 26, 2004 7:34 am

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
New poster
Posts: 8
Joined: Fri Sep 24, 2004 8:40 am

Post by vladimir manich » Sun Sep 26, 2004 9:13 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
Location: Bangladesh
Contact:

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

Post by TISARKER » Tue Nov 09, 2004 12:09 pm

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

Post by sklitzz » Mon Feb 14, 2005 11:12 pm

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;
}

Post Reply

Return to “Volume 1 (100-199)”