107 - The Cat in the Hat

[spork]

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[2][10] ={0};
int k=2;
int i=0;
while(n!=1) {
if(((unsigned long)n%k)==0) {
tmp[0][i]=k;
tmp[1][i]++;
n/=k;
}
else {
if(tmp[0][i]!=0) {
i++;
}
k++;
}
}
ans =1;
for(int j=0 ; j<=i ; j++) {
ans *= tmp [0][j];
}
times = tmp[1][0];
}

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]

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]

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]

(n+1)^k

n^k

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

[TuIgEv]

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
readln(h,num);
if (h = 0) and (num = 0) then break;
if h = 1 then begin
writeln('0 1');
continue;
end;
faht(h);
gcd := x[1];
for i := 2 to m do begin
gcd := euqlid(gcd,x);
end;
k := gcd div (x[1] 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]

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]

OK. Thanks. I'll try some interpolation methods to solve this system

[midra]

thanks a lot!
I would try to do it.
good luck!
bye!!

[Dumb]

81 64 is not a valid input my friend:-)
think about it.....

[Chung Ha, Yun]

I am a primer.

I want to solve a problem of 107.

However, I can't understand this problem unfortunately.

What do follow sentences mean?

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]

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]

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


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]

You are very helpful..

I got ACCEPTED.

[Chung Ha, Yun]

I can't read your code...ToT It is difficult to me...;;

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]

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
readln(x,y);
if(x=0)and(y=0)then break;
if x>1 then begin
b:=0;
repeat inc(b);
a:=round(exp(ln(x)/b));
until round(exp(ln(a-1)*b))=y;
end;
if x<3 then write(x-1)else write((Y-1)div(a-2));
writeln(' ',x*a-y*(a-1));
until 1=0;
end.[/pascal]