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

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

Post by emotional blind » Thu May 04, 2006 7:50 pm

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
Location: bangladesh

107

Post by mak(cse_DU) » Tue Jun 06, 2006 4:05 pm

why time limit exceed?

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

107 WA help plz.. :-(

Post by moon » Tue Jun 20, 2006 5:27 pm

what's wrong with this code .Plz help :cry:



#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

Post by moon » Wed Jun 21, 2006 6:46 am

[/quote] :cry: :cry:


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

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

Use some efficient functions.

Post by linux » Sun Jul 09, 2006 7:59 am

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

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

Thanks.

Post by linux » Sun Jul 09, 2006 1:06 pm

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

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

testcases!

Post by linux » Mon Jul 10, 2006 3:51 pm

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

Post by rk » Sun Aug 20, 2006 6:44 pm

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
New poster
Posts: 15
Joined: Sun Apr 30, 2006 10:19 am
Location: Lithuania

Post by nev4 » Sun Aug 20, 2006 9:51 pm

My AC code gives this:

4 37
LOOPS FOREVER
3280 242461

loops forever - should be wrong input.

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

Yah 107

Post by Tanu » Mon Aug 21, 2006 11:50 am

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:

Getting wrong answer, please help

Post by sangram » Fri Sep 29, 2006 5:23 pm

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

Post by nafi1212 » Sat Nov 04, 2006 9:55 pm

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?

Post by joehuang92 » Sat Nov 18, 2006 5:04 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by joy » Sun Dec 03, 2006 7:11 am

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

Post by nbauernf » Thu Mar 22, 2007 3:08 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).

Post Reply

Return to “Volume 1 (100-199)”