## 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
Contact:
Really? For

Code: Select all

``216 125``
I got

Code: Select all

``127 623``
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:
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
Contact:
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
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
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
Contact:
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
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

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

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

### 107 Test Data, WA

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 );
}
}``````
Narek Saribekyan
Narek Saribekyan

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
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
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 !!!
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
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 !!!
Narek Saribekyan

snar
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia
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
test data doesn't have this case!

Code: Select all

``````100 1
1000 1
10000 1
``````