## 107 - The Cat in the Hat

Moderator: Board moderators

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
Sorry For My Mistake,
I just checked your code with some random input
and compare the output of my accepted code,
Sorry, I had to be more careful

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm

### 107

why time limit exceed?

moon
New poster
Posts: 5
Joined: Mon Jan 02, 2006 12:49 pm
Contact:

### 107 WA help plz.. :-(

what's wrong with this code .Plz help #include <stdio.h>
//#include <conio.h>
//#include <dos.h>
//#include <stdlib.h>
//#include <string.h>
#include <math.h>

int main()
{
//clrscr();
long int t,l;
long int cat,hig;
int flag=0;

while(1)
{
scanf("%ld %ld",&l,&t);

if(t==0 && l==0)
break;

int N = 2 ,tem=0;
float q ,p,x,y,h,b ,f;

while( N <= sqrt(t) || N==2 )

{
if((l-t)==1)
{
cat=1,hig=t+l;
flag =3;
break;
}
if(t< 2 || l< 2)
{
if(t==1 &&l==1)
{
cat=0,hig=1;
flag =2;
}
else if(t==1 && l != 1)
{
hig= ((l-t)*N)+t;
f =(log10(l)/log10(2)) +0.5 ;
cat = f;
flag =2;
}
break;
}
x=log10(t),y =log10(l);
h =y/x;

q=log10(N) ,p =log10(N+1);
b=(p/q);

if(b == h )
{
flag =1;
tem = N;
break;
}

N++;
}

if(flag ==1)
{
cat = (t-1)/(N-1) , hig = ((l-t)*(N+1))+t;
printf("%ld %ld\n",cat,hig);
flag=0;
}
else if(flag==2)
{
printf("%ld %ld\n",cat,hig);
flag=0;
}
else if(flag==3)
{
printf("%ld %ld\n",cat,hig);
flag=0;
}

}
// getch();

return 0;
}
Last edited by moon on Wed Jun 21, 2006 7:00 am, edited 1 time in total.
moon

moon
New poster
Posts: 5
Joined: Mon Jan 02, 2006 12:49 pm
Contact:

### Re: 107 WA

[/quote]  I compile it in turbo C compiler in .cpp file . some of my input and out put is following----

input

1 1
2 1
4 1
1024 1
371293 248832
11 10
1 1
1048576 59049
483736625 481890304
125 64
1 0
64 1
5764801 1679616
100 1
1000 1
10000 1
0 0

out put

0 1
1 3
2 7
10 2047
22621 1840825
1 21
0 1
29524 4017157
615441 1931252289
21 369
1 1
6 127
335923 30275911
7 199
10 1999
13 19999

moon

linux
Learning poster
Posts: 56
Joined: Sat Jul 01, 2006 12:21 pm
Location: CA-95054
Contact:

### Use some efficient functions.

Because your program took too much time to generate the output file. May be it's because of an infinite loop or inefficient algorithm.

------------------------------------------------------
Smile for good health..

linux
Learning poster
Posts: 56
Joined: Sat Jul 01, 2006 12:21 pm
Location: CA-95054
Contact:

### Thanks. You are really great!
Thank you very much, Guru. Your hints really helped me very much.
Last edited by linux on Thu Jan 24, 2008 10:38 am, edited 1 time in total.
Solving for fun..

linux
Learning poster
Posts: 56
Joined: Sat Jul 01, 2006 12:21 pm
Location: CA-95054
Contact:

### testcases!

many users are getting WA frequently for this problem.
For which I'll tell you about some testcases that are
Input:

Code: Select all

``````1 1
216 125
5764801 1679616
1024 243
2 1
4 1
1024 1
371293 248832
11 10
1 1
1048576 59049
483736625 481890304
125 64
64 1
81 64
0 0``````
Output:

Code: Select all

``````0 1
31 671
335923 30275911
121 3367
1 3
2 7
10 2047
22621 1840825
1 21
0 1
29524 4017157
615441 1931252289
21 369
6 127
9 217``````
I was also getting WA for the reason that my program crashed for the cases like 100 1, 1 1 etc.
Solving for fun..

rk
New poster
Posts: 6
Joined: Thu Jul 06, 2006 7:51 pm

### WA in 107

my code gives right o/p 4 all test cases i encountered,
but i get WA by judge ....

code is

Code: Select all

``````# include <iostream.h>
# include <math.h>
int main()
{unsigned int h,i,a,b,c,fg;double d;
while(1)
{cin>>h>>i;
if(h==0 && i==0) break;
if(h==1 && i==0) cout<<"1 1\n";
else if(h==1) cout<<"0 1\n";
else if(h==2) cout<<"1 3\n";
else if(h==3) cout<<"1 4\n";
else if(i==h-1) cout<<1<<" "<<h+i<<"\n";
else {if(h%2==0 && i==1)
{d=log(h)/log(2);
if(pow(2,int(d))==h)
{cout<<int(d)<<" "<<(unsigned int)(h*(pow(0.5,int(d)+1)-1)/(-0.5))<<"\n";
continue;
}
for(a=h,fg=0,b=0,c=0;a!=1;)
if(a%2==0) {b++;c+=a;a/=2;}
else {fg=1;break;}
if(fg==0) {cout<<b<<" "<<c+1<<"\n";continue;}
}
for(a=3,fg=0;a<=h/2;a++)
if(h%a==0)
{d=log(h)/log(a);
if(h!=pow(a,int(d))) continue;
b=int(d);
if(pow(a-1,b)!=i) continue;
cout<<(i-1)/(a-2)<<" "<<h*a-i*(a-1)<<"\n";fg=1;
break;
}
if(fg==1) continue;
}
}
return 0;
}
``````
also kindly give the ans of
• 16 9
1771561 64
65536 6561
0 0
thanks

nev4
New poster
Posts: 15
Joined: Sun Apr 30, 2006 10:19 am
Location: Lithuania
My AC code gives this:

4 37
LOOPS FOREVER
3280 242461

loops forever - should be wrong input.

Tanu
Learning poster
Posts: 70
Joined: Sun May 29, 2005 12:46 pm
Location: Mars

### Yah 107

I found 3-4 wrong answer for this problem...
I used this algo...
k is initialized as 1...
find the k th root m of 1st number...
decrement to get z = m-1...
p = pow(z , k)
if (fabs(p-second number))
calculate results using k.....
............................................
.............................................
i was at wrong answer bcoz....
i did not think about any input with 1....
so check it.....
hope it helps

sangram
New poster
Posts: 8
Joined: Fri Jun 30, 2006 3:27 pm
Contact:

I am getting Wrong Answer in Problem 107 - The Cat in the Hat
Please someone help. Giving code below. I am basically seaching for a number n such that n divides the second input and (n+1) divides the first number. All such numbers n are then tested to be the correct solutions by finding the appropriate logarithms.
The code is given below:

Code: Select all

``````#include<iostream>
#include<cmath>
using namespace std;

int main(){
long long int a,b;
while(true){
cin >> a >> b;
if((a == 0) && (b == 0))
break;
if(a == 1){
cout << 0 << " " << 1 << endl;
continue;
}
if(b == 1){
cout << (int) ((log10(a) / log10(2)) + 0.5) << " " << 2*a-b << endl;
continue;
}
int i=2;
while(! (a % (i+1) == 0 && b % i == 0 &&
(((int) (log10(a) / log10(i+1) + 0.5)) == ((int) (log10(b) / log10(i) + 0.5)))))
i++;
cout << ((b-1) / (i-1)) << " " << (i+1)*(a-b) + b << endl;
}
return 0;
}
``````

nafi1212
New poster
Posts: 5
Joined: Sat Sep 02, 2006 10:33 pm

### 107 - RTE!!!!!!!!!!!! Help!! Plz!!

I donunderstand why i am getting Run time error (floating point exception).Here is my code-

Code: Select all

``````#include <cstdio>
#include <cmath>

using namespace std;

int main()
{
int Hgt;int worker;
int cats=0,height=0;
int m,N;
while(1){
scanf("%d %d", &Hgt, &worker);
if(Hgt==0)
break;

for(m=1;;m++){
double x=pow(pow((int)worker,1.0/m)+1,m);

double diff = fabs((Hgt+.0) - x);
if(diff<.000001)
break;
}

double temp = pow(worker,1.0/m);

N = (int)ceil(temp);
cats = ((worker-1)/(N-1));
double v =  (N+.0)/(N+1);
height = (int)(Hgt*(1-pow(v,m))/(1-v));

printf("%d %d\n", cats, height+(int)worker+1);
}

}``````

joehuang92
New poster
Posts: 9
Joined: Sat Nov 18, 2006 4:56 pm
Location: Taiwan
Contact:

### 107 TE?

I've tried so many times submitting my code but keep receiving TE...

But when it runs on my PC, every input data runs well(even for data such as 785^3 & 784^3), and every of it takes only less than 1 second to get results...

How can I reduced my execution? Here is my code...

Code: Select all

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

unsigned long initial_height;
unsigned long work_cat;

double rest_cat;
double total_h;

int const_n;
int const_h;

int i,j;

int find_const();

int main()
{
while( scanf(" %d %d",&initial_height,&work_cat)==2 )
{
const_n = 0;
const_h = 0;

rest_cat = 0;
total_h = 0;

if( initial_height==0 && work_cat==0 )
break;

if( work_cat !=1 )
find_const();
else
{
const_n = 2;
while( initial_height % 2 == 0 )
{
initial_height /= 2 ;
const_h++;
}
}

if( const_n != 2 )
rest_cat = ( pow( (const_n - 1) , const_h ) - 1 ) / ( const_n - 2 );
else
rest_cat = const_h;

if( const_n != 2 )
for( i=0 ; i<=const_h ; i++ )
total_h += pow( (const_n - 1) , i ) * pow( const_n , (const_h - i) );
else
total_h = pow( 2 , const_h + 1 ) - 1;

printf("%.0f %.0f\n",rest_cat,total_h);

}

return 0;
}

int find_const()
{
for( i=2 ; i<=800 ; i++ )
{
for( j=0 ; pow(i,j)<=initial_height && pow(i-1,j)<=work_cat; j++ )
{
if( pow(i,j)==initial_height && pow(i-1,j)==work_cat )
{
const_n = i;
const_h = j;
return 0;
}
}
}
}``````
Thx a lot!!

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Contact:

Code: Select all

``````float    -> "%f"
double -> "%lf"
long double -> "%Lf"
int -> "%d"
long -> "%ld"
long long -> "lld"
unsigned long -> "%lu"
unsigned -> "%u"
char -> "%c"``````
.................................
double pow(double a, double b); it returns double:
so change ..

Code: Select all

``pow(i,j)==initial_height //got TLE for this``
to

Code: Select all

``fabs(pow(i,j)-initial_height)<.000001``
.....................
u will get WA now
ur output wrong for :

Code: Select all

``````9 8
5 4``````
output sould:

Code: Select all

``````1 17
1 9``````
......................................

Code: Select all

``````The number of cats inside each (non-smallest) cat's hat is N,

so total_cat= 1 + N + N^2 + N^3 + ... + N^x
where, worker_cat = N^x
total_hight = 1 + (N+1) + (N+1)^2 + ... + (N+1)^x

given (N+1)^x and N^x
u have to find: (total_cat - worker_cat) (total_hight)``````
hope it helps..........
form kisui na ... class tai asol....
iF U hv d class u get the form....

nbauernf
New poster
Posts: 5
Joined: Thu Mar 08, 2007 4:33 am
Clearly if v is 1 then you have division by zero. Try a few test cases where N=1 (you should be able to produce the a and b values after picking a k value).