107 - The Cat in the Hat

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

[totobogy]

I just checked it by copying and compiling the code again it gives 31 671.
wat can be the problem?

[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!

[eg_frx]

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.

[eg_frx]

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.

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

[zero_cool]

I've got accepted already. I think so, too Mamun. Thx for helping me.

[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

[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

hint : use prime factoring and gcd..

[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

[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?

[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 !!!

[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 !!!

[snar]

My solution works in a linear time, but i'm sure that there's a solution in O(1). Anybody???

[IRA]

test data doesn't have this case!

Code: Select all

100 1 
1000 1 
10000 1