107 - The Cat in the Hat

[ram]

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]

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]

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]

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]

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]

whats the cause of rejection. Is it "Time limit exceeded"?

[ram]

thanks for your reply,

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]

Try "125 64" as input. Output should be "21 369".

[Rossi]

No wrong answer

[Stefan Pochmann]

Try input "1024 243". Output should be "121 3367".

[Rossi]

It is .. ok with ur input

[Stefan Pochmann]

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.

[vlad ionescu]

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
readln(ai,bi);
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]

My numerous experiences with this problem has only yielded one piece of advice. Use floating point at your own peril. I have yet to get a solution working with FP. I have 3 different solution methods with integers.

[C8H10N4O2]

As per my other post, this problem is very nasty about floating point rounding.