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

Scryer
New poster
Posts: 4
Joined: Fri Jul 11, 2003 12:17 am

Post by Scryer » Mon Jul 28, 2003 2:35 pm

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
New poster
Posts: 45
Joined: Mon Jul 14, 2003 9:42 pm
Location: Zoetermeer, The Netherlands

Post by El-idioto » Mon Jul 28, 2003 11:22 pm

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
New poster
Posts: 2
Joined: Sun Aug 17, 2003 9:30 am

Post by jimmyhezhang » Thu Aug 21, 2003 9:38 am

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

jimmyhezhang
New poster
Posts: 2
Joined: Sun Aug 17, 2003 9:30 am

Post by jimmyhezhang » Thu Aug 21, 2003 9:48 am

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

User avatar
bignad98
New poster
Posts: 6
Joined: Mon Sep 15, 2003 3:21 am
Location: Charleston, S.C.
Contact:

Post by bignad98 » Mon Oct 06, 2003 4:36 am

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.
"Moral victories are for girls!" -- Shawn Kiernan

"You can't spell geek without EE..." -- Larkin Gentry

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Mon Oct 06, 2003 9:41 am

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
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 » Fri Oct 10, 2003 5:09 pm

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).
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

serfan
New poster
Posts: 1
Joined: Mon Sep 22, 2003 12:23 pm
Location: Dhaka,Bangladesh
Contact:

help me about cat in the hat (107)

Post by serfan » Fri Oct 17, 2003 4:00 pm

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;
}
take care
Sarwar Erfan
Department of Computer Science and Engineering, BUET, Dhaka, Bangladesh

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

107 : "Cat in The Hat" WA ... ???

Post by Almost Human » Thu Oct 30, 2003 3:25 pm

I got WA on this problem ...

Does anybody can help me ??? :cry: :cry: :cry:

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
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Thu Oct 30, 2003 7:13 pm

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
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Thu Oct 30, 2003 7:14 pm

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
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human » Fri Oct 31, 2003 6:32 am

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

Can anybody explain it to me, please ?

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Fri Oct 31, 2003 12:12 pm

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
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human » Fri Oct 31, 2003 12:28 pm

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
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

107 The Cat in the Hat

Post by Sajid » Sat Nov 01, 2003 1:16 am

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?
Sajid Online: www.sajidonline.com

Post Reply

Return to “Volume 1 (100-199)”