107 - The Cat in the Hat

[famousun]

#include<iostream.h>
#include<math.h>
unsigned int idl , tot;
int js(int later,int sume,int height)
{
int temp , i ,j;
for(i = 2 ; i<=later ; i++)
{
temp = (int)(log(sume)/log(i) );
if((int)pow(i+1,temp) == height)
break ;
}
for(j=1; j <= temp ; j++)
{
tot += ((int)pow(i,j)*(int)pow(i+1,temp-j));
idl += (int)pow(i,j-1);
}

return (i) ;
}
void main()
{
unsigned int height, sum2, fi;
cin>>height>>sum2 ;
int later ;
while((sum2 != 0)&&(height != 0))
{
later = (int)sqrt(sum2) ;
if(sum2 == 1)
{
idl = 0 ;
tot = height ;
}
else if(height - sum2 == 1)
{
idl = 1 ;
tot = height + sum2 ;
}
else
{
idl = 0; tot = height;
fi = js(later,sum2,height) ;
}

cout<<idl<<' '<<tot<<endl ;
cin>>height>>sum2 ;
}
}
I have read someone's code and got some idea ,but It got WA
i 'm confused ,tell me why?
Thanks !

[16023]

I already read some posts before...but I still don't understand why the ouputs like this.
For example:
Input:3 2 Output: 1 5
Input:2 1 Output: 1 3
Input:3 3 Output: 1 5

where
Input: height of initial cat # of worker cat
Output: # of cats not working height of the stack of cats
why?

Thanks in advance

[sarig]

Hello!

Could someone tell me why I get WA on this? I works fine with every test I've made on my own computer. Every suggested test on this forum works fine.

[c]
int main(void) {
int N, h, c;
long th, toth, totc, tc;
double k;

while(scanf("%d %d", &h, &c) != EOF) {
if(h == 0 && c == 0)
break;
k = log(h)/log(c);
if(h == 1) {
printf("0 %d\n", c);
continue;
}
if(c == 1) {
printf("1 %d\n", h+1);
continue;
}
toth = h;
totc = 1;
N = 2;
while(log(N+1.0)/log(N) - k > 1e-15) N++;
tc = 1;
th = h/(N+1);
while(th > 1) {
tc *= N;
totc += tc;
toth += (th*tc);
th /= (N+1);
}
toth += c;
printf("%ld %ld\n", totc, toth);
}

return 0;
}
[/c]

Thanx,
Sarig

[Dominik Michniewski]

What's about cases of manner "2^N 1" ??

Dominik

[sarig]

These are my current test cases:

Input:

216 125
5764801 1679616
1024 243
2 1
4 1
1024 1
371293 248832
11 10
1 1
1048576 59049
483736625 481890304
125 64
1 0
64 1
0 0

Output:

31 671
335923 30275911
121 3367
1 3
1 5
1 1025
22621 1840825
1 21
0 1
29524 4017157
615441 1931252289
21 369
0 0
1 65

Cheers,
Sarig

[Dominik Michniewski]

all your output values for "2^N 1" are wrong ... except 2 1 )

my accepted solution produces other values:
i.e.
1024 1 ==> 10 2047
64 1 ==> 6 127

Good Luck

Dominik

PS. THink deeper about this cases ... I think, that this cases cause many people to wrong answer ....

[sarig]

Gaaa!

Thanx!

Remove the c==1 code and change N=2 to N=1 was enough (in the case where c==1 we have N=1 and the depth of the tree becomes log_2(h)).

Thanx again! I got it accepted now.

Cheers,
Sarig

[james-b]

I still got WA..
Here's my C code:
[c]#include<stdio.h>
#include<math.h>

void main()
{
double n,N,result1,result2,result3,result4;
/*"n" stands for the layers of the cats, "N" means the number of the cats in the hat*/

long input1,input2;
double a,b,c,i,j,multi1,multi2;
double exp=0;

while(scanf("%D%D",&input1,&input2)!=EOF)
{
if(input1!=0)
{
a=(double)input1;
b=(double)input2;
}

else if(input1==0&&input2==0)
break; /*if input="0 0" then quit*/

result3=0;
if(a>1&&b>1)
{
for(N=1;N<1000000;N++)
{
for(n=1;n<28;n++)
{
multi1=(double)pow(N+1,n);
multi2=(double)pow(N,n);
if(multi1==a&&multi2==b)
break;
/*the number of the smallest cats will be (N^n),and the biggest height will be (1*(N+1)^n) */ /*End of inner loop*/
}
if(multi1==a&&multi2==b)
break;
/*end of outer loop*/

}
result1=pow(N,n)-1;
printf("%ld ",(long int)(result1/(N-1)));
for(i=1,j=n;j>=0;i++,j--)
{
result2=pow(N+1,i-1)*pow(N,j);
result3=result2+result3;
}
printf("%ld\n",(long int)result3);

/*here using the term : a(r^n -1)/r-1 to sum the cats of non-working and the height of all*/
}
else if(b==1)
{
if(a!=1)
{
while(1)
{
if(pow(2.0,exp)==a)
break;
else
exp++;
}
result4=exp+1;
printf("%ld %ld\n",(long int)exp,(long int)pow(2.0,result4)-1);
exp=0;
}
else
printf("0 1\n");
}
else if(b==0)
printf("0 0\n");
}
}
[/c]

So I've tested all the data I could found and there was nothing wrong with my program....Will the input be bigger than 1000000^28?? Hope that's not the problem that makes it WA....

Beg for some help,please.

[epsilon0]

here's what i understood:

let
x = the number of cat generations
y = the number of cats in each hat
a = the height of the bigger cat
b = the number of worker cats

you need to solve the system:

(y+1)^x = a
y^x = b

where x and y are unknowns, and x y a b are all integers.

i seeked an analytical solution, but didn't find it. it might be that i'm too bad at math.

if anyone has an analytical solution to this problem, please post it.

i figured a way to solve it with the computer. one could compute the prime factors of a and b, and try to group them (perhaps computing the smallest common divisor of the powers of these prime numbers). but i feel like there must be something much more efficient....

[epsilon0]

the two things we are looking for are:

number of non-working cats:

sum(i=0 to x-1) (y^i)

total height of all stacked cats:

sum(i=0 to x) [ ( (y+1) ^ (x-i) ) * y^i ]

[anubis_kanuII]

1 100 is not valid. The worker cats have height 1, and the height of the inicial cat is 1. So, it's impossible to have 100 worker cats.


See ya

Anubis

[prilmeie]

I am confident that there exists a faster solution for this problem than brute force iterating, evaluationg the power and afterwards value checking. As we all know, the two input values, I will call them x and y are of the form (mathematical expressions in LaTeX style):

x = A^{k}
y = (A + 1)^{k}

The problem description asks for the solution of the following two sums:

\sum_{j = 0}^{k} ( A + 1 )^{j} * A^{k - j} = A^{k + 1} * ( ( \frac{ A + 1 }{A} )^{k+1} - 1 )

and:

\sum_{j = 0}^{k - 1} A^{j} = \frac{A^{k} - 1}{A - 1}

For those who do not know LaTeX:

• _ means next block is subscripted
• ^ means next block is superscripted
• \sum means the sum of (a.ka. upper greek sigma)
• \frac means a fraction, first block is the numerator, second block is the denominator
• braces (resp. curly brackest or {}) are used to declare blocks.

Now let me now show you what I already know about A, k, x and y:

1. Obviously x and y are multiples of A
2. y - x - 1 is a multiple of A, too (Presumly, if k is prime, y - x - 1 is also divisible by k, i.e. y-x-1=kA). You can prove this one by the binomial theorem.
3. Therefore z = ggT(x, y - x - 1) is also a multiple of A.

I know, this is not too much, but does this help anyone for further investigations? - I think even if there does not exists a fast (O(1)) algorithmic solution for this problem, these observations and some conclusions from your side on this subject might help to get a much smaller set of candidates for A and k.

Regards,
Franz

[razibcse]

My program seems to give correct result for all possible values..
but i mgettin WA...
someone pls help me with input file or suggestions....

Code: Select all

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

void main()
{
long n,n2,m,level,a,flag;
double temp,height_of_stack,num_of_worker;
double height_of_first,non_working;
float rev,n1;

for(;;)
{
scanf("%lf %lf",&height_of_first,&num_of_worker);
if(height_of_first==0 && num_of_worker==0)
  break;

if((height_of_first-num_of_worker)==1.0)
   printf("%ld %.0lf\n",1,(height_of_first+num_of_worker));
else
 {
flag=1;
for(m=2;m<=31;m++)
 {
 rev=1.0/m;

 n1=pow(num_of_worker,rev);
 n2=(long)n1;

 if((n1-n2)<1.0)
   {
   if(height_of_first==pow((double)(n2+1),m))
      {
      n=n2;
      level=m;
      flag=0;
      }
   }
  if(!flag) break;

 }

 temp=n-1;

 non_working=(num_of_worker-1)/temp;
 height_of_stack=0;

 for((a=0,m=level);a<=level;(a++,m--))
   height_of_stack+=(pow((double)n,a)*pow((double)(n+1),m));

 printf("%.0lf %.0lf\n",non_working,height_of_stack);
 }
}
}

:[c][/c]

[Ivor]

I don't quite understand it -- it's been quite some time I solved and optimized this problem... There does exist O(1) solution -- it's not mathematical though. It is possible to hash all possible input values and thus have a look-up table.

Ivor

[prilmeie]

It is possible to hash all possible input values and thus have a look-up table.

This is exactly the kind of solution which I do not want to submit - using precalculated values. Allthough this solves the problem, it does not respect the spirit and the intention of the problemset. But I do not want to start a discussion here about the "spirit" of the problemset. If one feels alright with this kind of solution there is no reason for me to complain about it.

My intention is a more mathematical point of view. I want to analyze those problems to the uttermost, in order to develop an elegant solution. I am considering a solution as elegant if it is an excellent tradeoff between both time and memory use and the least possible source code. So you could see me as an idealist, if you want.

Regards,
Franz