Page 16 of 19

Posted: Sat Jan 14, 2006 1:56 pm
by mamun
Really? For

Code: Select all

216 125
I got

Code: Select all

127 623
with your code.
Check it yourself with the code you have posted.

Posted: Sat Jan 14, 2006 2:50 pm
by totobogy
I just checked it by copying and compiling the code again it gives 31 671.
wat can be the problem?

Posted: Sat Jan 14, 2006 3:58 pm
by mamun
Check this line

Code: Select all

if((unsigned long) pow(n,(double)1/d)+1 == (unsigned long) pow(h,(double)1/d))
Can you find the mistake now?
I wonder how you got correct answer in your computer with this mistake!

Posted: Tue Jan 17, 2006 4:02 am
by eg_frx
mamun wrote:Check this line

Code: Select all

if((unsigned long) pow(n,(double)1/d)+1 == (unsigned long) pow(h,(double)1/d))
Can you find the mistake now?
I wonder how you got correct answer in your computer with this mistake!
I got the correct answer for this case, too. It may be computer dependent.

Posted: Tue Jan 17, 2006 4:04 am
by eg_frx
totobogy wrote:I just checked it by copying and compiling the code again it gives 31 671.
wat can be the problem?
The problem is indeed in the line that mamum quoted. One of the reasons is that the floating point->integer cast is not a rounding operation. There are other subtlties to fix too.

Posted: Tue Jan 17, 2006 10:16 am
by mamun
Actually casting isn't the problem.
if((unsigned long) pow(n,(double)1/d)+1 == (unsigned long) pow(h,(double)1/d))
Where this 1 should be added? If I place this 1 into correct place then I get correct answer with totobogy's code.

Posted: Sat Jan 21, 2006 5:26 pm
by zero_cool
I've got accepted already. I think so, too Mamun. Thx for helping me.

Re: Tests to 107

Posted: Sat Mar 25, 2006 9:46 am
by Hope1001
Sample INPUT
1 1
16 9
65536 6561
216 125
5764801 1679616
0 0

Sample OUTPUT
0 1
4 37
3280 242461
31 671
335923 30275911

Posted: Sun Apr 02, 2006 7:14 am
by suhendry
This problem can be solved without using floating-point data type. I figured this one out after getting alot of WA when using float/double to solve this problem :P

hint : use prime factoring and gcd..

107 Test Data, WA

Posted: Wed May 03, 2006 7:15 pm
by snar
Hi,
i have WA and need some test data to debug my code (it's hard to make a test for this problem, yeah?).

Anyway i'm posting my code too, maybe someone would want to debug it himself.

Code: Select all

#include <stdio.h>
#include <math.h>

void main() {
	int x, y, h, n, r, s ;	
	double c, l; 	
	while ( scanf ("%d%d", &x, &y ) ) {
		if (x==0 && y==0) break ;
        c = log ( (double)x )/log ( (double)y ) ; 
		for ( n=1; n<=y; n++ )
		if ( fabs( pow( (double)n,c )-(double)n-1.0 ) < 0.001 ) break ;
		
		h = (int)(log ( (double)y )/log ( (double)n )) ;
		
		r = (int)(pow ( (double)n,(double)h+1 )-1)/(n-1) - y;		
		l = n/(double)(1+n);		

		s = (int) ( x*( pow ( l,(double)(h+1) )-1 )/(double)(l-1) + 0.001);
		printf ( "%d %d\n", r, s );		
	}
}
Thanks in advance,
Narek Saribekyan

Posted: Wed May 03, 2006 9:23 pm
by emotional blind
I give u some input and output of my accepted code.

INPUT

Code: Select all

100 1 
1000 1 
10000 1 
0 0
OUTPUT

Code: Select all

7 199 
10 1999 
13 19999
Your program produce different output..
Do you need any more help?

Posted: Thu May 04, 2006 2:27 pm
by snar
no, i think i found my bug. the problem is the second number - 1, i have division by zero.

got it!!!
btw. your input was wrong - it is not possible to build a tree with that parameters, anyway, you helped me to find my mistake, thanks very much :D!!!

Posted: Thu May 04, 2006 3:51 pm
by snar
got it!!!
btw. your input was wrong - it is not possible to build a tree with that parameters, anyway, you helped me to find my mistake, thanks very much :D!!!

Posted: Thu May 04, 2006 3:54 pm
by snar
My solution works in a linear time, but i'm sure that there's a solution in O(1). Anybody???

Posted: Thu May 04, 2006 3:58 pm
by IRA
test data doesn't have this case!

Code: Select all

100 1 
1000 1 
10000 1