## 107 - The Cat in the Hat

Moderator: Board moderators

spork
New poster
Posts: 1
Joined: Fri Dec 26, 2003 11:28 pm

### HELP 107 WA

I pass every possible inputs I think. However I still get WA

Could anyone tell me what's wrong?

thanks.

[cpp]#include <iostream>
#include <cmath>
#include <stdlib.h>
using namespace std;

void solve(double,double);
void divs(double,double&,double&);
double gcd(double,double);

int main() {
double n,k;
//FILE* fp = fopen("C://input.dat","r");
//fscanf(fp,"%d %d",&n,&k);
cin>>n>>k;
//cout<<n<<k;
while(n!=0 || k!=0) {
//cout<<n<<k;
solve(n,k);
//fscanf(fp,"%d %d",&n,&k);
cin>>n>>k;
}
//system("PAUSE");
return 0;
}
void divs(double n,double& ans,double& times) {
if(n==1) {
ans =1;
times =1;
}
int tmp ={0};
int k=2;
int i=0;
while(n!=1) {
if(((unsigned long)n%k)==0) {
tmp[i]=k;
tmp[i]++;
n/=k;
}
else {
if(tmp[i]!=0) {
i++;
}
k++;
}
}
ans =1;
for(int j=0 ; j<=i ; j++) {
ans *= tmp [j];
}
times = tmp;
}

double gcd(double a, double b ){
return b==0 ? a : gcd( b, (unsigned long)a%(unsigned long)b);
}

void solve(double first,double total) {
double ans1,ans2=0;
double k,times,k1,times1;
if(first ==1) {
cout<<"0"<<" "<<total<<endl;
return;
}

divs(first,k,times);
divs(total,k1,times1);

if(total!=1) {
double gcd1 = gcd(times,times1);
k = (double)pow((double)k,(double)(times/gcd1));
times = gcd1;
}
double r= k-1;
if(r!=1)
ans1 = (double)((pow((double)r,(int)times)-1)/(r-1));
else
ans1 = times;
for(int i=0 ; i<=times ; i++) {
ans2+=(double)(first*pow((float)r,i));
first/=k;
}
cout<<(int)ans1<<" "<<(int)ans2<<endl;
}[/cpp]

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

### 107- The cat in the Hat. TLE. Inputs and outputs are ok!!!!!

ok...I am a beginner so my code is surely ugly and ineficient... but I don't understand what I have to do in this particular case because I have test all the sample input and output, and all the inputs/outputs that I have read in this forum and it seems to be ok....maybe I am forgetting some special case or something like this.
if any one can help me I would be eternallly grateful!! Here is my code:

[c]
#include <stdio.h>
#include <math.h>

int main()
{
double height,workers,t,i,cant=1,temp,alt=0,x,n;
empieza:
cant=1, alt=0;
scanf("%lf %lf", &height, &workers);
if (height==0 && workers==0)
return 0;
else if (height==1 || height==0)
{
printf("0 %.0lf\n", workers);
goto empieza;
}

else
{
temp=height;
for (n=1; n<=4000; n++)
{
t=n;
for (i=1; i<=30; i++)
{
if (n*t==workers)
{
if (pow(n+1,i+1)==height)
{
for (x=1; x<i+1; x++)
{
temp=temp/(n+1);
cant+=pow(n, x);
alt+=pow(n,x)*temp;
}
printf("%.0lf %.0lf\n", cant, alt+height+workers);
goto empieza;
}
else
t=n*n;
}
else
{
for (t=1; t<=4000; t++)
{
for (x=1; x<=30; x++)
if (pow(t+1,x)==height)
{
if (pow(t,x)==workers)
{
for (n=1; n<x; n++)
{
temp=temp/(t+1);
cant+=pow(t, n);
alt+=pow(t,n)*temp;
}
printf("%.0lf %.0lf\n", cant,alt+height+workers);
goto empieza;
}
}
}
}

}
}

}
}
[/c]

any suggestions

ranjit
New poster
Posts: 34
Joined: Fri Jan 30, 2004 11:22 am
Location: india
i didnt read ur code but i guess u found that u have to evaluate n and k when (n+1)^k and n^k are given.

use prime factorization to reduce the number of iterations.

bye and good luck.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
(n+1)^k

n^k
Or you can use Newtons's method to solve the equations for n and k.

TuIgEv
New poster
Posts: 4
Joined: Mon Mar 01, 2004 12:21 pm

### 107 TL in CATS

Help! Need a LITTLE help. I have got TL in problem 107 (about cats and hats). Maybe my algorithm is really slow?

I present height of initional cat as prime numbers degrees. After than finding all possible n's

[pascal]
program zzz;
var i,j,k,m,s,min,gcd : longint;
h,num,l,sum,r,n,t : int64;
p,x : array [1..100000] of longint;

procedure faht(h : int64);
var i,s : longint;
begin
fillchar(x,sizeof(x),0);
m := 0;
s := trunc(sqrt(h))+1;
for i := 2 to s do begin
if h mod i = 0 then begin
inc(m);
p[m] := i;
end;
while h mod i = 0 do begin
h := h div i;
inc(x[m]);
end;
end;
if h > 1 then begin
inc(m);
p[m] := h;
x[m] := 1;
end;
if m = 0 then begin
inc(m);
x[m] := 1;
p[m] := 1;
end;
end;

function euqlid(a,b : longint) : longint;
var r : longint;
begin
if a > b then begin
r := a;
a := b;
b := r;
end;
r := b mod a;
if r = 0 then euqlid := a else euqlid := euqlid(a,r);
end;

function count(k : longint) : int64;
var i,j : longint;
y : int64;
begin
y := 1;
for i := 1 to m do begin
for j := 1 to (x div gcd)*k do begin
y := y*p;
end;
end;
count := y;
end;

begin
while true do begin
if (h = 0) and (num = 0) then break;
if h = 1 then begin
writeln('0 1');
continue;
end;
faht(h);
gcd := x;
for i := 2 to m do begin
gcd := euqlid(gcd,x);
end;
k := gcd div (x div gcd);
for i := 1 to k do begin
if k mod i <> 0 then continue;
n := count(i);
n := n-1;
r := 1;
for j := 1 to k div i do begin
r := r*n;
end;
if r = num then begin
s := k div i;
break;
end;
end;
l := 1;
sum := h;
r := 1;
t := h;
for i := 1 to s do begin
r := r*n;
if i <> s then begin
l := l+r;
end;
t := t div (n+1);
sum := sum+r*t;
end;
writeln(l,' ',sum);
end;
end.
[/pascal]

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
Well, this method is indeed slow.

What should do is try to derive the two equations.

(n+1)^x = a;
n^x = b;

where a and b are the input.

You should sove it by mathematical methods and not a bruteforce approach.

TuIgEv
New poster
Posts: 4
Joined: Mon Mar 01, 2004 12:21 pm
OK. Thanks. I'll try some interpolation methods to solve this system

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:
thanks a lot!
I would try to do it.
good luck!
bye!!

Dumb
New poster
Posts: 2
Joined: Sun Mar 07, 2004 10:36 pm
81 64 is not a valid input my friend:-)

Chung Ha, Yun
New poster
Posts: 19
Joined: Tue Jul 16, 2002 5:56 pm
Location: Seoul
Contact:

###  I can't understand...ToT Plz help me.

I am a primer.

I want to solve a problem of 107.

However, I can't understand this problem unfortunately.

The number of cats inside each (non-smallest) cat's hat is a constant, N. The height of these cats-in-a-hat is 1/(N+1) times the height of the cat whose hat they are in.
Plz help a primer...ToT

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
This means, suppose the height of the tallest cat is 16 and N is 1.

So the number of cats inside this cats hat is 1( the value of N ). The height of this cat is 1*16/(N+1) or 16/(1+1) = 8;

This cat will have more cats( in this case 1 ) inside its hat.

Of course this is a simple example, because the value of N could be larger than this. However, be assured that the input will be valid, that is the formula will ultimately lead to the smallest cat(s) height to be 1.

Dumb
New poster
Posts: 2
Joined: Sun Mar 07, 2004 10:36 pm

### Plz help me out for 107

I just don't know why i am getting time exceed error  any one plz point out the error...
i have tried all possible inputs that i could find on this site
and ALL of them go just like any thing...
i simply cann't understand what the hech is wrong ... [cpp]#include<iostream>
#include<stdio>
#include<stdlib>
#include[itex]

typedef unsigned long int ui;
ui pw(ui n,ui ex)
{
if(ex==1)
return n;
return n*pw(n,ex-1);
}

ui ch(ui h,int m)
{
if(h==1)
{
return h;
}
else{
ui s=h;
for(int i=0;i<m;i++)
{
s+=ch(h/(m+1),m);
}
return s;
}
}

void exp(ui b,ui a)
{

ui volatile num=a;
volatile ui ex=0;
ui x,s=b;
//for the case of leaf==1
if(a==1)
{
for(volatile int i=1;pw(2,i)<=b;)
{
if(s%2==0)
{
ex=i;
i++;
s/=2;
}
else if( (s%2) != 0 )
{
return ;
}
}
if(ex<1)
return;
if(pw(2, ex )==b)
{
ui sa=ex;
cout<<sa<<" "<<ch(b,1)<<endl;
return ;
}
return ;
}
//for any other case
x=2;

while(x<=num)
{
if(num%x==0)
{
num/=x;
ex++;
}
else if((num%x)!=0)
{
x++;
if(ex>0)
{
ex=0;
num=a;
}
}
}

if(pw(x+1,ex)==b)
{
ui s=( (a-1) / (x-1) );
// cout<<endl<<(ui)(log((double)a)/log((double)x))<<endl;/*levels of tree*/
cout<<s<<" "<<ch(b,x)<<endl;
return ;
}
return;
}

int main(){
ui h=1,l=1;

for (;l && h;)//while(l!=0 && h!=0)
{
cin>>h>>l;
if(h==0 && l==0)
{
return 0;
}
else if(h==0 || l==0)
{
l++;
h++;
}
else
{
exp(h,l);
}
}
return 0;
}[/cpp]

Chung Ha, Yun
New poster
Posts: 19
Joined: Tue Jul 16, 2002 5:56 pm
Location: Seoul
Contact:

### Thank you^^

You are very helpful.. I got ACCEPTED.

Chung Ha, Yun
New poster
Posts: 19
Joined: Tue Jul 16, 2002 5:56 pm
Location: Seoul
Contact:

### ^-^

I guess that your solution is brute force.

I got Accepted using brute force, but I optimize a fomula.

I used log function.

Of course, Brute force is not good solution.

Newton's method is better solution than brute force.

QulinXao
New poster
Posts: 29
Joined: Mon Apr 05, 2004 11:12 am

### Good but WA

here good solution but WA what wrong:
get x y
where x==a^b (1) and y==(a-1)^b (2)
sheach b with this property: exp(ln(exp(ln(x)/b) -1)*b)==y
then out is:
((a-1)^b-1)/(a-1-1) and (a^(b+1)-(a-1)^(b+1))/(a-(a-1)) or same

(y-1)/(a-2) and a*x-(a-1)*y

[pascal]var x,y,a,b:int64;begin repeat