107 - The Cat in the Hat

[Krzysztof Duleba]

To my surprise it came out that my program should exceed the time limit as system logarithm is very, very slow - much slower than couting a power in linear time. I changed a few things and now everything is OK.
BTW: it's a bit strange that all the posts in this thread are mine, itn't is?

[chunyi81]

I am trying to solve problem 107 in Java, but the online judge kepps on giving me time limit exceeded. Could someone help please? Below is my code:

[java]import java.io.*;
import java.util.*;
class Main {

static String ReadLn (int maxLg)
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}

catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null);
return (new String (lin, 0, lg));
}

public static void main(String[] args) throws IOException {

String line;

while((line = ReadLn(255)) != null) {

StringTokenizer st = new StringTokenizer(line);

int height = Integer.parseInt(st.nextToken());
int num = Integer.parseInt(st.nextToken());

//We have a pair of simultaneous eqns -
//height / ((N + 1) ^ m) = 1 - eqn 1
//N ^ m = num - eqn 2
//Imagine a full m-ary tree and at level m,
//we have 'num' children.
//Take log on both sides for both eqns -
//rearranging, we get -
//m * log (N + 1) = log(height) - eqn 3
//m * log N = log(num) - eqn 4
//eqn 3 / eqn4 - we can solve for N -
//log(N + 1) = (log(height) / log(num)) * log N
//by trial and error
//with the value of N, we can solve for m using
//either eqn 3 or eqn 4

if ((height > 0) && (num > 0)) {

if ((height > 1) && (num > 1)) {

int test = 2;
boolean found = false;
double value = Math.log(height) / Math.log(num);

while(!found) {

if (test + 1 - Math.pow(test,value) < 1E-15)
found = true;

else test++;

}

int temp = 1;
int total = 1;
int total_height = 0;
int h = 1;

while (num >= 1) {

total_height += (h * num);
temp *= test;

if (num > test)
total += temp;

h *= (1 + test);
num /= test;

}

System.out.println(total + " " + total_height);

}

else if ((height == 1) && (num == 1))
System.out.println(0 + " " + num);

else if ((height > 1) && (num == 1)) {

int m = (int)(Math.log(height) / Math.log(2));
int test = 1;
int total = 1;
int temp = 1;
int total_height = 0;

for (int i = 1;i < m;i++) {
total_height += (height * temp);
temp *= test;
total += temp;
height /= 1 + test;
}

for (int j = m - 1;j <= m;j++) {
total_height += (height * temp);
temp *= test;
height /= 1 + test;
}

System.out.println(total + " " + total_height);

}

}

else break;

}

}

}[/java]

I have found inputs which my program takes very long to process - very large integers within the range of int - For example 100000000 99999999. I believe the bottleneck is in the while loop getting the root. Could anyone who have solved this problem suggest a more efficient way other than to get the root by brute force? Thanks.

[einstain000]

Code: Select all

#include<stdio.h>

void main() {
	int i ,j;  // auto var
	unsigned long height;  //initial cat's height
	unsigned long works;  // the cat work
	unsigned long total;  //total height
	unsigned long rest ;  //the cat rest
 
	while(scanf("%lu %lu",&height,&works)) {
      /* end condition (0,0) */
		if( height == 0 && works == 0 )
			break;

      /* special condition ( 1,x)*/
		if( height == 1 ) {
			printf("0 %d\n",works);
			continue;
		}

		for( i = 2; ; i++ ) {
			unsigned long temp = height;
         /* find a num which can divide height */
			for(j = 1 ;; j++) {
				temp /= i;
				if( temp <= 1) 
					break;
			}
			if( temp <= 1 ) {
				temp = 1;
            /* check the num  , see if it can divide workers */ 
				for(int k = 1 ; k <= j ; k++){
					temp *= ( i - 1);
				}
				if( temp == works)
					break;
			}
		}


      /* add all worker(rest) and all cats' height */
		unsigned long temp = 1, temp2 = height;
		total = rest = 0;
		for( int m = 0 ; m <= j ; m++) {
			total += temp * height;
			if( m != j)
				rest += temp;
			temp *= ( i - 1 );
			height /= i;
		} 
		printf("%ld %ld\n",rest,total);
	}
}

I have test any inputs about 107....
but it still get WA!

Someone can help me ?
sorry .. my English is not good , so ... you may hard to understand
what i say ... but please help me to get AC . Thx

[shamim]

one suggestion is to use a double data type rather than int or unsigned int.
see if this works.

[knight823]

Can anyone help me??
My program get Time Limit Exceeded
but I don't know why??

[cpp]
#include <iostream>
#include <math.h>
#include <fstream>
using namespace std;

void main()
{
while(cin)
{
int high=0,work=0,allhigh,nowork;
cin>>high>>work;

if(high==0&&work==0)
break;
else if(high==1&&work==0)
{
cout<<"0"<<" "<<"1"<<endl;
continue;
}
else if(high==1*(work+1))
{
cout<<"1"<<" "<<high+work<<endl;
continue;
}
else
{
int N=1,x=1,www=1,hhh=high;

while(N<=work)
{
if(log(work)*log(N+1)==log(high)*log(N))
break;
else
N++;
}
allhigh=high;
nowork=1;
while(hhh!=1||www!=work)
{
hhh/=(N+1);
www*=N;
nowork+=www;
allhigh+=(www*hhh);
x++;
}
cout<<nowork-work<<" "<<allhigh<<endl;


}

}
}

[/cpp]

Can help me ? thanks^^

[Ryan Pai]

I assumed that the input is of the format:

height=(N+1)^a
workers=(N)^a

for some positive integer N

I did include as a special case, height=1,workers=x, but it only seems logical to me that x=1 is the only valid input. (of course I checked that value on my code without the special case and it broke it).

But with these assumptions it is possible to get an accepted solution.

[shamim]

ur program takes far too long to even run the sample input.
You should change your algorithm.

[SilVer DirectXer]

i am Time Limit too.
But my code run fast...
why?[cpp]
#include <stdio.h>
#include <math.h>
int alpha,N,height,rest_c,a,b;
int finished;
int ans1;
double ans2;
int i;
void main(void)
{

while (1)
{
scanf("%d",&height);
scanf("%d",&rest_c);
if (height==0 && rest_c==0)
break;
if (height==1)
{
printf("0 %d\n",rest_c);
continue;
}
if (rest_c==0)
{
printf("0 0\n");
continue;
}
finished=0;
for (N=1;N<9999999;N++)
{
for (alpha=1;alpha<9999999;alpha++)
{
a=(int)pow((int)N,(int)alpha);
b=(int)pow((int)N+1,(int)alpha);
if (b>height || a>rest_c)
break;
if (a==rest_c && b==height)
{
finished=1;
break;
}
}
if (finished==1)
break;
}

ans1=1;
for (i=1;i<alpha;i++)
{
ans1+=(int)pow(N,i);
}


ans2=0;
for (i=0;i<=alpha;i++)
{
ans2+=(float)pow(N/(double)(N+1),i);
}
ans2*=height;

printf("%d %.0lf\n",ans1,ans2);
}

}


[/cpp]

[Zhao Le]

I don't understand the float error in my code.

Why the code not break the loop while the test code 216 125
I don't understand, hope somebody help me.

PS> here is not the full code just the sample.

[cpp]#include <iostream.h>
#include <math.h>

void main()
{
while(1)
{
int height,cats; // height means height of initial cat
// cats means the number of worker cats
// pow(n+1,a)=216
// pow(n,a)=125
cin>>height>>cats;
if(height==0&&cats==0) break;
int a=1;
long double m,n;
while((m-n)!=1)
{
m=exp(log(height)/a);
n=exp(log(cats)/a);
//cout<<m-n<<endl;
//if(m==1+n) break; // ??? maybe wrong in some cases
a++;
}
/*int notwork=0; // the number of cats that not work
int sum=0; // height of the stack of cats
int N=1;
a++;
while(a--)
{
if(a) notwork+=N;
sum+=N*(int)height;
N*=(m-1); // why (int)m=6 (int)n=4???
height/=m;
}
cout<<notwork<<" "<<sum<<endl;*/
}
}[/cpp]

[shamim]

The method u r using is quite inappropriate.

The best method is to form two equations with two unknowns; ( N,x)
where N has its defined meaning x is related to the number of different types of cats( cats of various heights).

Use the two equations to solve for N and then find the value of x.
Good Luck.

[Zhao Le]

My Equation is
pow(n,a)=216 // height
pow(n+1,a)=125 // cats

How can I solve other way besides above my code?

[El-idioto]

Hi all,

I got a wrong answer every time!
I checked my application with all the numbers I found in the forums, and they all work:

Input:
1 14
1 0
1 1
2 1
4 1
8 1
11 10
16 1
216 125
1024 243
1024 1
7776 3125
14641 10000
16807 7776
371293 248832
390625 65536
1048576 59049
5764801 1679616
100000000 99999999
0 0


Output:
0 14
0 0
0 1
1 3
2 7
3 15
1 21
4 31
31 671
121 3367
10 2047
781 31031
1111 61051
1555 70993
22621 1840825
21845 1690981
29524 4017157
335923 30275911
1 199999999

Any suggestions?


[cpp]
// @JUDGE_ID: 33444KK 107 C++
//
// 107_CatInTheHat: Determine which cats are not working, and the height of all cats
//

#include <cstdio>
#include <cmath>

// The base types
typedef char int8;
typedef short int16;
typedef long int32;
typedef unsigned char uint8;
typedef unsigned short uint16;
typedef unsigned long uint32;

// The maximum amount of layers to be checked
#define MAX_LAYERS 32


//------------------------------------------------------------------------------------// F U N C T I O N S
//------------------------------------------------------------------------------------

// This function determines whether 2 doubles are (approximately) equal
bool AreEqual(double dA, double dB, double dEpsilon) { return (dA > dB - dEpsilon) && (dA < dB + dEpsilon); }


//------------------------------------------------------------------------------------

// This function is the entrance of the app
int main()
{
uint32 u32HeightBiggestCat, u32TotSmallestCats;

// Get the next input parameters
while((scanf("%d %d", &u32HeightBiggestCat, &u32TotSmallestCats) == 2) && u32HeightBiggestCat > 0)
{
// Do we have the special case that the biggest cat is of height 1?
if(u32HeightBiggestCat == 1) printf("0 %u\n", u32TotSmallestCats);
else
{
uint8 u8TotLayers = 0;
uint32 u32CatsPerHat, u32TotNonWorkerCats, u32TotHeightAllCats;

// Set the initial state
u32CatsPerHat = u32TotSmallestCats;

// Find a combination for which it holds that : (CatsPerHat+1)^TotLayers == HeightBiggestCat
// where CatsPerHat and TotLayers are whole numbers
do
{
double dCatsPerHat;

// Find a combination for which it holds that : CatsPerHat^TotLayers == TotSmallestCats
// where CatsPerHat and TotLayers are whole numbers
do
{
// Get the amount of smallest cats (N^L)
u8TotLayers++;
dCatsPerHat = pow((double)u32TotSmallestCats, 1.0 / (double)u8TotLayers);
u32CatsPerHat = (uint32)dCatsPerHat;
}while(u8TotLayers <= MAX_LAYERS && !AreEqual(dCatsPerHat, (double)u32CatsPerHat, 0.0001));

}while(u8TotLayers <= MAX_LAYERS && !AreEqual(pow(double(u32CatsPerHat + 1), (double)u8TotLayers), (double)u32HeightBiggestCat, 0.0001));

// Calculate the total number of non-worker cats and the sum of the heights of all the cats
u32TotNonWorkerCats = 1;
u32TotHeightAllCats = u32HeightBiggestCat;
for(uint8 u8Layer=1;u8Layer<=u8TotLayers;u8Layer++)
{
uint32 u32CatsOnThisLayer, u32HeightPerCat;

// Add the number of cats on this layer to the total
u32CatsOnThisLayer = (uint32)pow((double)u32CatsPerHat, (double)u8Layer);
u32TotNonWorkerCats += u32CatsOnThisLayer;

// Add the height of each cat on this layer to the total
u32HeightPerCat = (uint32)pow(double(u32CatsPerHat+1), double(u8TotLayers-u8Layer));
u32TotHeightAllCats += u32HeightPerCat * u32CatsOnThisLayer;
}

// Exclude the worker cats
u32TotNonWorkerCats -= u32TotSmallestCats;

// Show the result
printf("%u %u\n", u32TotNonWorkerCats, u32TotHeightAllCats);
}
}

return 0;
}
[/cpp]

[Scryer]

Input:

Code: Select all

216 125
0 0

My AC program's output:

Code: Select all

31 671

Your output:

Code: Select all

4294967205 215

Good luck!

[El-idioto]

Dear Scryer,

216 125 results in 31 671 for my code!
To make sure nothing went wrong when copy'n'pasting
my code to this forum I copied it back and recompiled it.
I use Visual Studio.NET 2003 as compiler. What do you use?

The numbers mentioned above the code are really what
I get when running my app.

Does any one see an error with the input / output, or
maybe knows an input which is 'sneaky'?

Help very much appreciated.

[Scryer]

I use Visual Studio.NET 2003 as compiler. What do you use?

I compiled your program with the gcc (g++) compiler v. 3.2.1 under Linux. It gives the same result that you reported for your other test cases, but not for this one.