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

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

Post by ram » Sun Mar 10, 2002 1:57 am

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:

Post by Stefan Pochmann » Sun Mar 10, 2002 11:26 am

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:

Post by lundril » Wed Mar 20, 2002 2:57 am

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:

Post by ftomi » Wed Mar 20, 2002 1:35 pm

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

Post by Rossi » Thu Mar 21, 2002 8:53 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:

Post by ram » Thu Mar 21, 2002 9:40 am

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

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

Post by ram » Thu Mar 21, 2002 9:58 am

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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Thu Mar 21, 2002 12:08 pm

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

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

Post by Rossi » Thu Mar 21, 2002 12:24 pm

No wrong answer

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Thu Mar 21, 2002 12:30 pm

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

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

Post by Rossi » Thu Mar 21, 2002 12:34 pm

It is .. ok with ur input

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Thu Mar 21, 2002 12:45 pm

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
New poster
Posts: 2
Joined: Sun Mar 17, 2002 2:00 am

Post by vlad ionescu » Sat Mar 23, 2002 11:28 pm

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
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Sun Mar 24, 2002 6:07 am

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
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Sun Mar 24, 2002 6:16 am

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

Post Reply

Return to “Volume 1 (100-199)”