107 - The Cat in the Hat

[emotional blind]

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)]

why time limit exceed?

[moon]

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;
}

[moon]

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

[linux]

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]

You are really great!

Thank you very much, Guru. Your hints really helped me very much.

[linux]

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.

[rk]

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

please help

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]

My AC code gives this:

4 37
LOOPS FOREVER
3280 242461

loops forever - should be wrong input.

[Tanu]

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]

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]

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]

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]

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

[nbauernf]

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