107 - The Cat in the Hat

[Scryer]

I found your problem running under linux/gcc: the double->u32 conversion truncates downward in your inner loop on this case. I imagine the libraries are enough different that you were unlucky this time. Try modifying it as follows:

Code: Select all

u32CatsPerHat = (uint32)(dCatsPerHat + .0001);                                                                                                

[El-idioto]

Hi Scryer,

Your the best ever! That was indeed it.
I changed the line
[cpp]
u32CatsPerHat = (uint32)dCatsPerHat;
[/cpp]
to
[cpp]
u32CatsPerHat = (uint32)floor(dCatsPerHat + 0.5);
[/cpp]
and I got accepted!

I was very surprised I didn't get accepted the first time, since I was quite convinced this was a very simple problem.
Then when I checked all the values I found on the forums (and they were correct on my machine), I was certainly at a loss.

Many thanks again!

[jimmyhezhang]

does the test data '1 14' make any sense?

[jimmyhezhang]

i why '0 0' is the answer of '1 0'? isn't it '0 1'.

[bignad98]

There is an analytic solution of sorts, although i have no idea of it's efficiency. if you express the two equations with natural logs, you'll get an equation of the form N^c - N -1 = 0, where N is the number of cats in each hat and c is the ratio of the natural logs of the two input constants. You can use numerical analysis to derive an approximation for N and then use N to solve for the tree depth. However, i have no idea what the actual process is (or even if it is efficient) -- i just know it exists, because you can use a math program like Maple to solve the above equation. just thought i would throw it out -- i would love to know the details if anyone can point me in a good direction.

[shamim]

Here is one way to solve it.

Having the two equations:

(N+1)^x=a --(1)
N^x=b --(2)

now from (1) x=log(a)/log(N+1).

from (2) x= log(b)/log(N);

therefore log(a)/log(N+a)=log(b)/log(N);

this is an equation where N is the only unknown, with a and b as input.

It is easy to solve this using Newton's Method, as log function has a simple deravitives.

[epsilon0]

this problem is stupid.

input (1,#) (where # different from 1) makes no sense.

if the top level cat has height 1, then there can be no other cat, and the top level cat is a worker cat (the only one).

thus the only acceptable (1,#) input is (1,1) and the answer is obviously 0 1.

input (#, 0) makes no sense. there are always workers cats.

either give me an explanation or i give up. this is very disappointing that the input data for this problem violates the problem statement specifications.

the problem clearly states that there is always one, and only one top level cat, and there are always worker cats also (at least 1).

[serfan]

i can't find why i am getting WA with this solution. it gives correct outputs(i think) please any one suggest me something

Code: Select all

#include<iostream.h>

int prime[25]={
		2,3,5,7,11,
		13,17,19,23,29,
		31,37,41,43,47,
		53,59,61,67,71,
		73,79,83,89,97
		};
int main(){
	unsigned long int l,wc,N,I,nwc,sl,k,i;
	while(1){
		unsigned long int occ[25]={0,0,0,0,0,
					   0,0,0,0,0,
					   0,0,0,0,0,
					   0,0,0,0,0,
					   0,0,0,0,0
					   };
		cin>>l>>wc;
		if((l==0)&&(wc==0)) return 0;
		if(l==1){
			cout<<0<<1<<endl;
			continue;
		}
		k=wc;
		for(i=0;i<25;i++){
			while(k%prime[i]==0){
				occ[i]++;
				k/=prime[i];
			}
		}
		N=1;
		for(i=0;i<25;i++)
			if(occ[i]){
				I=occ[i];
				N*=prime[i];
			}
		while((l%(N+1))){///this
			N*=N;
			I/=2;
			}           ///this
		nwc=1;
		k=1;
		for(i=1;i<I;i++){
			k*=N;
			nwc+=k;
		}
		sl=l;
		unsigned long int l2=l;
		k=N;
		for(i=1;i<I+1;i++){
			l2/=(N+1);
			sl+=(k*l2);
			k*=N;
		}
		cout<<nwc<<" "<<sl<<endl;

	}
	return 0;
}

[Almost Human]

I got WA on this problem ...

Does anybody can help me ???

What should be the output for such input :
0 1
0 10
0 100
1 1
100 1
1000 1
10000 1

any special input I should consider ??

[Maarten]

My AC program crashes on the first 3 tests; for the other tests I get the following output:
0 1
7 199
10 1999
13 19999

Hope this helps

[Maarten]

Some extra tests:

input:

Code: Select all

1 1 
100 1 
1000 1 
10000 1 
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:

Code: Select all

0 1
7 199
10 1999
13 19999
31 671
335923 30275911
121 3367
1 3
2 7
10 2047
22621 1840825
1 21
0 1
29524 4017157
615441 1931252289
21 369
1 1
6 127

[Almost Human]

I wonder why "7 199" should be the output for input "100 1"

Can anybody explain it to me, please ?

[Maarten]

I think 100 1 is invalid input, since 100 is not n^3 for any n.
But my program calculates as follows: we end with one worker cat, so the number of cats inside a bigger cat should be 1. Since the first cat has height 100, the second has height 1/(1+1) * 100 = 50, the 3rd 25, and now we run into problems.
Anyway, my method of solving yields the values 7 199, but i don't think you need to consider this test case

[Almost Human]

If so, I couldn't figure it out why my program keep gives me WA ....

please help

Code: Select all

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

#define maxLayer 32

int main ( void )
{
  unsigned long initialHeight , numOfSmallestCat , numOfSmallerCat , layer , result1 , result2 , i ;
  double catPerHat , epsilon = ( double ) 0.0001 ;

  /*freopen ( "107.in" , "r" , stdin ) ;
  freopen ( "107.out" , "w" , stdout ) ;*/

  while ( scanf ( "%lu %lu" , &initialHeight , &numOfSmallestCat ) != EOF )
  {
	if ( initialHeight == 0 && numOfSmallestCat == 0 ) break ;
    if ( initialHeight == 1 ) printf ( "0 %d\n" , numOfSmallestCat) ;
    else
    {
      for ( layer = 1 ; layer <= maxLayer ; layer ++ )
      {
		  catPerHat = pow ( numOfSmallestCat , ( double ) 1.0 / layer ) ;

		  if ( catPerHat - floor ( catPerHat ) > epsilon ) continue ;
		  if ( fabs ( pow ( catPerHat + 1 , layer ) - initialHeight ) < epsilon ) break ;
      }
      numOfSmallerCat = floor ( catPerHat ) ;

	  if ( numOfSmallerCat == 1 ) result1 = layer ;
	  else result1 = ( pow ( numOfSmallerCat , layer ) - 1 ) / ( numOfSmallerCat - 1 ) ;

	  result2 = 0 , i = 1 ;

	  do
	  {
		  result2 += i * initialHeight ;

		  if ( initialHeight == 1 ) break ;

		  initialHeight /= ( numOfSmallerCat + 1 ) ;
		  i = i * numOfSmallerCat ;
	  }
	  while ( 1 ) ;

      printf ( "%lu %lu\n" , result1 , result2 ) ;
    }
  }

  return 0 ;
}

[Sajid]

I got WA. I matched every inputs and outputs in this forum. any1 give some critical inputs?

what will be the maximum height of the tree?