Page 8 of 16

Posted: Wed Jun 08, 2005 6:02 am
by sumankar
I got AC with unsigned long long.And I am not too sure how the judge feels about __int64.

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

Posted: Wed Jun 08, 2005 6:11 am
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.

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

Posted: Thu Jun 09, 2005 2:14 am
by cOsMo
CODE REMOVED

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

Posted: Thu Jun 09, 2005 6:23 am
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.

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

Posted: Thu Jun 09, 2005 2:08 pm
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.

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

Posted: Thu Jun 09, 2005 2:39 pm
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.

Posted: Thu Jun 09, 2005 6:40 pm
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...

Posted: Fri Jun 10, 2005 6:07 am
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.

tnx

Posted: Sun Jun 12, 2005 2:41 pm
by cOsMo
It works...Tnx

[147]

Posted: Tue Jan 31, 2006 6:46 pm
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...

Posted: Wed Feb 01, 2006 10:28 am
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. 

Posted: Wed Feb 01, 2006 3:36 pm
by Dimitar
Thanks, it works now!!! Although I don't understand the problem with the precision...

147 compile error

Posted: Thu Mar 30, 2006 7:59 pm
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?

Posted: Fri Mar 31, 2006 4:50 am
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.

WA

Posted: Sat Apr 01, 2006 6:19 pm
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