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

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar »

I got AC with unsigned long long.And I am not too sure how the judge feels about __int64.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Re: 147 __int64 can't hold big results.Please help

Post by sumankar »

There are other problems in your code...
cOsMo wrote:

Code: Select all

#include <cstdio>
#include <iostream>
I do see you have mixed cin/printf, but I don't understand why. I believe you have good reasons for doing so, otherwise its better to stick to
printf/scanf or cin/cout - for consistency's sake.

Code: Select all

#define MAX_N 6000
#define M 11
using namespace std;


int coins[]={1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 4000};
I dont think you have read the problem description very well...

Code: Select all

	  double input;
	  cin>>input;  if (input==0.00) break;
Dont actually need double, and if you do use double you can't do a == operation on floating point operands.Its best avoided, otherwise add some tolerance before doing so.

Code: Select all

          #define EPS 1e-13
           ...
	  double input;
	  cin>>input;  
          if ( fabs(input) < EPS ) break;
HTH
Suman.

cOsMo
New poster
Posts: 8
Joined: Fri Dec 10, 2004 11:04 pm
Location: Split , Croatia

Re: 147 __int64 can't hold big results.Please help

Post by cOsMo »

CODE REMOVED
Last edited by cOsMo on Sun Jun 12, 2005 2:42 pm, edited 1 time in total.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Re: 147 __int64 can't hold big results.Please help

Post by sumankar »

cOsMo wrote:

Code: Select all

if (input<EPS) break;
?
cOsMo wrote:

Code: Select all

	  printf( "%6.2lf%17lld\n", input, ways[ n ] ); 
should be

Code: Select all

	  printf( "%6.2lf%17llu\n", input, ways[ n ] ); 
Not really for input > 62.00 but at least for the last input 300.00, your program prints a different result than mine.

cOsMo
New poster
Posts: 8
Joined: Fri Dec 10, 2004 11:04 pm
Location: Split , Croatia

Re: 147 __int64 can't hold big results.Please help

Post by cOsMo »

cOsMo wrote:

Code: Select all

if (input<EPS) break;
Program should stop if input<EPS...Why did you put "?"

My program had wrong results after last coin was used.That was because my coins array was wrong. The correct one is:

int coins[]={1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000};


Finaly, my code was not accepted even with unsigned long long so i made a bignum class and got accepted... Tnx for your help sumankar.
Last edited by cOsMo on Thu Jun 09, 2005 6:34 pm, edited 1 time in total.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Re: 147 __int64 can't hold big results.Please help

Post by sumankar »

cOsMo wrote:

Code: Select all

if (input<EPS) break;
...
Program should stop if input<EPS...Why did you put "?"
Do you understand why I told you to add EPSin the very first place?I hope you do.I suggested a way, since you deviated a bit, I was wondering why.
cOsMo wrote:

Code: Select all

int coins[]={1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, [b]2000[/b]};
cOsMo wrote: I think you did not read it very well.
So I'll not have to go buy a pair of specs!You scared me :D

Code: Select all

#include <cstdio>
 ...[snipped]
  return 0;
}
cOsMo wrote: Since everything in the input will be of a form 5*x you can divide everything by 5 and save memory and time. :)
My AC code is 23 lines long.And it is in simple C.I changed your code a bit and it got AC'ed in 0.045 sec, using as much as 64K mem.
And, remove AC code asap, please.

cOsMo
New poster
Posts: 8
Joined: Fri Dec 10, 2004 11:04 pm
Location: Split , Croatia

Post by cOsMo »

I learned something new. You can't do this - float==something :D ,and I understand why you suggested EPS. Please PM the changed code so i can see what changes have you made...I was having MUCH trouble finding out my error, got tired and made BigNum -> got AC, so I think my error is not algorithmic. Tnx again...

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar »

Reading in input

Code: Select all

 int dec, frac, n;
 while( 2 == scanf("%d.%d",&dec, &frac) ) {
      n = dec * 100 + frac;
      if ( !n )
          break;
      /* Note I am indexing to n/5 th element here,
      ** to be consistent with your code,
      ** will land you  with RTE otherwise
      */
      printf("%6.2f%17llu\n",((float)n/100.0f),ways[n/5]);
  }
...is the only change that I made to your earlier WA code that was using unsigned long long.Note the input description says: that the input is a number of the form dd.ff and taking advantage of that fact, we can avoid the double & EPS stuff (I hate it :wink:).I will leave it as an exercise for you to figure out how to incorporate this in your code.But once you do
remove it from the board.Atleast the algorithm...
Suffice it to say that avoid double & floats as and when you can and use fixed point arithmetic.Its faster, cleaner and easier.

cOsMo
New poster
Posts: 8
Joined: Fri Dec 10, 2004 11:04 pm
Location: Split , Croatia

tnx

Post by cOsMo »

It works...Tnx

Dimitar
New poster
Posts: 8
Joined: Tue Sep 20, 2005 11:42 am

[147]

Post by Dimitar »

It works on my computer, but on the judge it gives a WA. I've read all the topics for this problem and I still can't find out what is wrong :(

Code: Select all

Deleted code...
Last edited by Dimitar on Wed Feb 01, 2006 3:36 pm, edited 1 time in total.

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

Post by IRA »

m:= trunc (r * 100+0.000001); <---- have some problem....
double precision problem....

Code: Select all

program dollars; 
const 
      n = 11; 
      k = 30000; 
      c: array [1..n] of integer = ( 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000 ); 

var 
    b: array [1..k] of qword; 
    r: real; 
    i, j, m: longint; 

begin 
     b[0]:= 1; 
     for i:= 1 to k do b[i]:= 0; 

     for i:= 1 to n do 
         for j:= c[i] to k do 
             b[j]:= b[j] + b[j-c[i]]; 

     readln (r); 
     while r <> 0 do begin 
           m:= trunc (r * 100+0.000001); 
           writeln (r:6:2, b[m]:17); 
           readln (r); 
     end; 

end. 

Dimitar
New poster
Posts: 8
Joined: Tue Sep 20, 2005 11:42 am

Post by Dimitar »

Thanks, it works now!!! Although I don't understand the problem with the precision...

snar
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia

147 compile error

Post by snar »

i've got compile error with this message

04461645_24.c: In function `int main()':
04461645_24.c:16: warning: assignment to `int' from `double'
04461645_24.c:25: implicit declaration of function `int wprintf(...)'

and here is my code

Code: Select all

// 147 Dollars

#include <stdio.h>
#define MAXTOTAL 10000

long long nway[MAXTOTAL+1];

int coin[11] = { 2000,1000,400,200,100,40,20,10,4,2,1 };

int main() {
  double f;
  int i,j,n,v,c;
  while (1) {
	  scanf("%lf", &f);
	  if (f == 0.00) break;
      n = f/0.05;
	  for (i=0; i<=n; i++) nway[i] = 0;
      v = 11;
      nway[0] = 1;
	  for (i=0; i<v; i++) {
		c = coin[i];
		for (j=0; j<=n-c; j++)
			nway[j+c] += nway[j];
     }
     wprintf(L"%6.2lf %17.lld\n", f, nway[n]);                  
  }
  return 0;
}
why compile error?
Narek Saribekyan

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 »

It seems that these two lines are causing some problems:

Code: Select all

n = f/0.05; 
f is a double and divideing by 0.05 still gives a double but you are assiging to an int. You should explicitly cast f/0.05 to an int and not expect the OJ compiler to do it for you. Somehow it should but it doesn't.

The other thing is you are using wprintf. According to the Unix manual for gcc, I find that you have one header library you did not include. Include wchar.h to remove this error. However, I am not sure if the OJ supports this.You can actually use printf in place of wprintf.

snar
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia

WA

Post by snar »

chunyi81, i've changed "wprintf" to "printf" but WA! (btw wchar.h didn't help).
1. Are sure that "printf" can lead to PE?
2. Haven't you solved this problem or haven't you meet problems with formatted outputs?
3. If yes, can't you look at my code (it is too short!).
4. Or someone else?
5. And also, the problem says.
Input will consist of a series of real numbers no greater than $300.00 each on a separate line. Each amount will be valid, that is will be a multiple of 5c. The file will be terminated by a line containing zero (0.00).
The problem statement is unclear. ex. starting from input about "50.00" my output becomes very big. But this is not a big integer problem, right?

I mean, if my solition is right then using coins
{ 2000,1000,400,200,100,40,20,10,4,2,1 } you can find uncountable number of solutions for 300.00 / 0.05 ($0.05 = 5c).

6. So, input is given in $-s, right?
7. If so, why I'm getting WA? (good finishing at seven)

Code: Select all

// 147 Dollars

#include <stdio.h>
#define MAXTOTAL 10000

long long nway[MAXTOTAL+1];

int coin[11] = { 2000,1000,400,200,100,40,20,10,4,2,1 };

int main() {
  double f;
  int i,j,n,v,c;
  while (1) {
	  scanf("%lf", &f);
	  if (f == 0.00) break;
      n = (int)(f/0.05);
	  for (i=0; i<=n; i++) nway[i] = 0;
      v = 11;
      nway[0] = 1;
	  for (i=0; i<v; i++) {
		c = coin[i];
		for (j=c; j<=n; j++)
			nway[j] += nway[j-c];
     }
     printf("%.2lf %lld\n", f, nway[n]);                  
  }
  return 0;
}
Thanks in advance
Narek Saribekyan

Post Reply

Return to “Volume 1 (100-199)”