## 107 - The Cat in the Hat

Moderator: Board moderators

ram
New poster
Posts: 30
Joined: Wed Mar 06, 2002 2:00 am
Contact:
Whats wrong with this code? I am getting
"Time limit exceeded error"?? Can any one help me??
#include <stdio.h>
#include <math.h>
#include <iostream.h>

using namespace std;

int number;
long double cinht;
long double inht,wornum;
int gen;
long double N;

int main(){

int i;

while((cin>>inht>>wornum))
{
if(inht==0&&wornum==0) break;
if(inht!=1)
{
N=1;
gen = 0;

while(pow(N,gen)!=wornum&&inht!=(pow((N+1),gen)))
{
N++;
gen = (int)(log(wornum)/log(N));
}

number = 0;
cinht =0;
for(i=0;i<gen;i++)
{

cinht+=inht*pow((1/(N+1)),i)*pow(N,i);
number+=pow(N,i);
}
cinht+=inht*pow((1/(N+1)),i)*pow(N,i);
}
else
{
cinht = wornum;
number = 0;

}

printf("%d %.0f n",number,cinht);

}
return 0;

}

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
I think you're recalculating powers too much. But that's not your problem. You might miss the correct value due to rounding errors. But that's still not the real problem.

Question: What makes the tree size (asymptotically) grow faster? Increasing the degree or increasing the height? It's inverse is slower so you'll find it faster in a brute force search.

Hope that helps. I don't want to give away the whole solution, but if I just confused you, please tell me.

lundril
New poster
Posts: 6
Joined: Tue Mar 19, 2002 2:00 am
Contact:
After three wrong answers here some
questions:
Besides checking all these not very
well defined border cases
(for example is it possible to have
a cat of height 1 in the BEGINNING,
that means only one worker cat
and none else (I can't see that
it is stated that the initial cat
can't be a worker cat) ?):

Is there any limit on the height of
the initial cat ?
(for example is something like
height:
143503601609868434285603076356671071740077383739246066639249
worker cats:
2955204414547681244658707659790455381671329323051646976
allowed ?)

What should I do if the numbers don't
make any sense like for example
10 10 (not possible)

so long
lundril

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:
1. It's possibile that the initial cat haven't got helper cats, in this case, this cat is an worker-cat.
2. I used unsigned int for height of the initial cat, the number of worker cats and for answers, so the asked numbers are not allowed.
3. The input doesn't contain impossibile numbers. (My program would hanged if there were some impossibile cases in the input.)

Rossi
New poster
Posts: 20
Joined: Thu Mar 21, 2002 2:00 am
it got accepted long ago .but after rejudge it went wrong..i can't find why? help plz..

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

void main()
{
register unsigned long int i,j;
unsigned long int h1,w,toth,idle;
double temp;

while(1){
scanf("%lu%lu",&h1,&w);
if(h1==0&&w==0)
break;

if(h1==1){
idle=0;
toth=w;
}
else if(h1-w==1){
idle=1;
toth=h1+w;
}
else{
idle=1;
toth=h1+w;
for(i=2;i<=sqrt(w);i++){
temp=log(w)/log(i);
if(pow(i+1,temp)==h1)
break;
}
for(j=1;j<temp;j++){
toth+=(pow(i,j)*pow(i+1,temp-j));
idle+=pow(i,j);
}
}
printf("%lu %lun",idle,toth);
}
}

ram
New poster
Posts: 30
Joined: Wed Mar 06, 2002 2:00 am
Contact:
whats the cause of rejection. Is it "Time limit exceeded"?

ram
New poster
Posts: 30
Joined: Wed Mar 06, 2002 2:00 am
Contact:

here is my new program. It should be really faster than my previous one. But I am getting wrong answer. Do u think its rounding errors again?
#include <iostream.h>
#include <math.h>
#include <iomanip>

using namespace std;

int main(){

double inht,workn,finht,N;
double gen,number,i;
while(cin>>inht>>workn){
if(inht==0&&workn==0) break;
if(inht!=1)
{
gen=1;

while(ceil(pow(inht,1/gen))-floor(pow(workn,1/gen))>1.00000000000000000000000000000001)
gen++;

N=pow(workn,1/gen);

number=0;
finht=0;

for(i=0;i<gen;i++)
{
finht+=inht*pow((1/(N+1)),i)*pow(N,i);
number+=pow(N,i);
}
finht+=inht*pow((1/(N+1)),i)*pow(N,i);

}
else
{
number=0;

finht=1*workn;
}

cout<<setiosflags(ios::fixed)<<setprecision(0)<<number<<" "<<finht<<endl;
}

return 0;
}

<font size=-1>[ This Message was edited by: ram on 2002-03-21 22:52 ]</font>

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Try "125 64" as input. Output should be "21 369".

Rossi
New poster
Posts: 20
Joined: Thu Mar 21, 2002 2:00 am

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Try input "1024 243". Output should be "121 3367".

Rossi
New poster
Posts: 20
Joined: Thu Mar 21, 2002 2:00 am
It is .. ok with ur input

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
No, your program prints "273 1838", at least on my computer. Since my computer in the past proved to behave very similar to the judge computer, I guess this might be a problem.

New poster
Posts: 2
Joined: Sun Mar 17, 2002 2:00 am
I get the same problem... It also works fine on my computer, anyone can help me with this?
I use BP7.0 on an Athlon 800MHz)

program catinhat(input, output);
const e=1.00001; e2=0.99999;
var ai,bi,n,x,i,j,k,sh,sn:longint;
a,b,xr,yr:extended;
begin
while not eof(input) do begin
if (ai<>0) and (bi<>0) then begin
x:=0; a:=ai; b:=bi;
if abs(ai-bi)=1 then x:=1
else
begin
j:=2; k:=1000;
repeat
i:=(j+k) div 2;
xr:=exp(1/i*ln(a)); yr:=exp(1/i*ln(b));
if (abs(xr-yr)<=e) and (abs(xr-yr)>=e2) then begin
x:=i;
n:=round(yr);
break;
end
else if abs(xr-yr)>e then j:=i+1
else k:=i-1;
until j>k;
end;
if x<>0 then begin
sh:=ai+bi; j:=1; sn:=1; k:=ai;
for i:=1 to x-1 do begin
j:=j*n; k:=k div (n+1);
sn:=sn+j; sh:=sh+j*k;
end;
writeln(sn:1,' ',sh:1);
end; { if x<>0 }
end; { if ai<>0 and bi<>0 }
end; { while }
end.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am