107 - The Cat in the Hat

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

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Sat Jan 14, 2006 1:56 pm

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
New poster
Posts: 7
Joined: Wed Jan 11, 2006 10:08 pm
Location: India
Contact:

Post by totobogy » Sat Jan 14, 2006 2:50 pm

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

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Sat Jan 14, 2006 3:58 pm

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
New poster
Posts: 21
Joined: Sat Oct 02, 2004 2:17 pm

Post by eg_frx » Tue Jan 17, 2006 4:02 am

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.

eg_frx
New poster
Posts: 21
Joined: Sat Oct 02, 2004 2:17 pm

Post by eg_frx » Tue Jan 17, 2006 4:04 am

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.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Tue Jan 17, 2006 10:16 am

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
New poster
Posts: 27
Joined: Fri Sep 02, 2005 6:33 am

Post by zero_cool » Sat Jan 21, 2006 5:26 pm

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

Hope1001
New poster
Posts: 1
Joined: Sat Mar 25, 2006 9:37 am
Contact:

Re: Tests to 107

Post by Hope1001 » Sat Mar 25, 2006 9:46 am

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
New poster
Posts: 14
Joined: Sat Aug 31, 2002 6:55 am

Post by suhendry » Sun Apr 02, 2006 7:14 am

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

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

107 Test Data, WA

Post by snar » Wed May 03, 2006 7:15 pm

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
Narek Saribekyan

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Wed May 03, 2006 9:23 pm

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
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia

Post by snar » Thu May 04, 2006 2:27 pm

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!!!
Last edited by snar on Thu May 04, 2006 3:52 pm, edited 1 time in total.
Narek Saribekyan

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

Post by snar » Thu May 04, 2006 3:51 pm

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!!!
Narek Saribekyan

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

Post by snar » Thu May 04, 2006 3:54 pm

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

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

Post by IRA » Thu May 04, 2006 3:58 pm

test data doesn't have this case!

Code: Select all

100 1 
1000 1 
10000 1 

Post Reply

Return to “Volume 1 (100-199)”