## 107 - The Cat in the Hat

**Moderator:** Board moderators

### Questioning input...

How can 65535 be a proper input? The problem is based on the two inputs being of the form:

(N+1)^k and N^k

65535 has a prime factorization of 3, 5, 17, 257. So, how does this work for the problem? That means that N would have to be each of these numbers, but N is a constant number, not a variant.

???

(N+1)^k and N^k

65535 has a prime factorization of 3, 5, 17, 257. So, how does this work for the problem? That means that N would have to be each of these numbers, but N is a constant number, not a variant.

???

### Suggestion...

Check out the input of "1 1". You are getting a funky result.

Hope this helps.

Ron

Hope this helps.

Ron

### ...

I ran my program again, and I come up with the following:

390625 65535 -> 21845 1690980 (instead of 1690981)

ALL of my other answers are right. I am still not following why we would have to worry about this case because 4^8 is 65536, and 5^8 is 390625???

390625 65535 -> 21845 1690980 (instead of 1690981)

ALL of my other answers are right. I am still not following why we would have to worry about this case because 4^8 is 65536, and 5^8 is 390625???

### Ignore...

Ignore that last bit of code. I figured out what is wrong with it. It is still getting a wrong answer, but don't know why now.

### TLE

I didn't debug all of your code, but I would think your bottleneck is the while loop, where you are using several log functions at once. This is very time consuming to a machine...and with division as well!

### [107] Need help to figure this out...

I have posted replies to several people on this problem. I have ran my program against several inputs, all from this site, and my program answers every one of them correctly. I have tested this program with every possible set of data I can find, or make up, including the extreme cases. However, the online judge says that I have an incorrect answer ("Wrong Answer"). If you have solved this problem, let me know what is wrong with mine and give me some kind of clue as to what is wrong, because I just cannot see it.

[cpp]//---------------------------------------------------------------------------

// Ron Buchanan

// ACM Volume I - #107

// "The Cat in the Hat"

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

#include <math.h>

#include <stdlib.h>

#include <stdio.h>

#define DEBUG 0

void findTheRoot();

long bigCatHeight;

long workerCats;

long theRoot;

double thePower;

long theLazyCats;

long theStackHeight;

long theHeight;

long cats;

void main()

{

while (true) {

scanf("%ld %ld", &bigCatHeight, &workerCats);

if (bigCatHeight == 0 && workerCats == 0) break;

if (bigCatHeight == 1) {

theLazyCats = 0;

theStackHeight = workerCats;

}

else {

// initialize

theRoot = 1;

thePower = log(bigCatHeight)/log(workerCats);

theLazyCats = 1;

theStackHeight = bigCatHeight;

// try to somewhat brute-force the root

findTheRoot();

#if DEBUG

printf("%ld^%f\n", theRoot, thePower);

#endif

// calculate the height of the stack and the number of lazy cats

theHeight = bigCatHeight / (theRoot+1);

cats = 1;

while (theHeight > 1) {

cats = cats * theRoot;

theLazyCats += cats;

theStackHeight += (long)(theHeight*cats);

theHeight = theHeight / (theRoot+1);

#if DEBUG

printf("%ld %ld %ld %f\n", cats, theLazyCats, theStackHeight, theHeight);

#endif

}

theStackHeight += workerCats;

/* OLD

theLazyCats = (long)((pow(theRoot, thePower+1) - 1)/(theRoot - 1)

- workerCats);

theStackHeight = 0;

for (int i = 0; i <= thePower; i++)

theStackHeight +=

(long)(pow(theRoot, i)*pow(theRoot+1, thePower-i));

*/

}

printf("%ld %ld\n", theLazyCats, theStackHeight);

}

}

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

// attempt to brute-force the root and power

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

void findTheRoot() {

while (log(theRoot+1)/log(theRoot) - thePower > 1e-15) {

theRoot++;

}

thePower = (long)(log(workerCats)/log(theRoot));

}[/cpp]

Any and all help would be greatly appreciated. [/cpp]

[cpp]//---------------------------------------------------------------------------

// Ron Buchanan

// ACM Volume I - #107

// "The Cat in the Hat"

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

#include <math.h>

#include <stdlib.h>

#include <stdio.h>

#define DEBUG 0

void findTheRoot();

long bigCatHeight;

long workerCats;

long theRoot;

double thePower;

long theLazyCats;

long theStackHeight;

long theHeight;

long cats;

void main()

{

while (true) {

scanf("%ld %ld", &bigCatHeight, &workerCats);

if (bigCatHeight == 0 && workerCats == 0) break;

if (bigCatHeight == 1) {

theLazyCats = 0;

theStackHeight = workerCats;

}

else {

// initialize

theRoot = 1;

thePower = log(bigCatHeight)/log(workerCats);

theLazyCats = 1;

theStackHeight = bigCatHeight;

// try to somewhat brute-force the root

findTheRoot();

#if DEBUG

printf("%ld^%f\n", theRoot, thePower);

#endif

// calculate the height of the stack and the number of lazy cats

theHeight = bigCatHeight / (theRoot+1);

cats = 1;

while (theHeight > 1) {

cats = cats * theRoot;

theLazyCats += cats;

theStackHeight += (long)(theHeight*cats);

theHeight = theHeight / (theRoot+1);

#if DEBUG

printf("%ld %ld %ld %f\n", cats, theLazyCats, theStackHeight, theHeight);

#endif

}

theStackHeight += workerCats;

/* OLD

theLazyCats = (long)((pow(theRoot, thePower+1) - 1)/(theRoot - 1)

- workerCats);

theStackHeight = 0;

for (int i = 0; i <= thePower; i++)

theStackHeight +=

(long)(pow(theRoot, i)*pow(theRoot+1, thePower-i));

*/

}

printf("%ld %ld\n", theLazyCats, theStackHeight);

}

}

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

// attempt to brute-force the root and power

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

void findTheRoot() {

while (log(theRoot+1)/log(theRoot) - thePower > 1e-15) {

theRoot++;

}

thePower = (long)(log(workerCats)/log(theRoot));

}[/cpp]

Any and all help would be greatly appreciated. [/cpp]

### Ignore my previous posts...

My program worked fine. I transfered everything to Unix. Got rid of any invisible characters in the code, and everything worked fine.

Windows

Anyway, I am just glad it is working.

Windows

Anyway, I am just glad it is working.

check:

1. use unsigned int rather than double for precision, if you use double, make sure there is no possible ways of precision error.

2. boundary cases, ex: 1 1 -> 0 1

3. invalid references like v[i-1], C++ probably will let you pass, but the judge will not. In the judge system, all memory other then the program is cleared. v[i-1] = 0. Although that's not likely in this program.

If it doesn't work still, I can put some more test cases

### Thanks

Thank you for the response, but as it turns out, I got it accepted. As it turns out, I put the code over to Unix, and loaded it in vi. I removed all Windows characters, and then resubmitted. After that, everything worked.

Again, thanks for the comments.

Again, thanks for the comments.

### 107 WA

Why this code got WA@@?

Code: Select all

```
[cpp]#include <iostream.h>
#include <math.h>
int check(int,int);
int check(int In,int arg)
{
int intS=0;
while (In%arg==0)
{
In/=arg;
intS++;
}
return intS;
}
int main()
{
unsigned long int intIn1,intIn2;
unsigned long int intT;
unsigned long int intS1,intS2,intA1,intA2,intSum;
while (cin >> intIn1 >> intIn2 )
{
if (intIn1==0 && intIn2==0)
break;
intA1=0;
intA2=0;
if (intIn1==1 && intIn2==1)
{
cout << "0 1" << endl;
continue;
}
for (intT=3 ;intT<intIn2 ;intT++)
{
intS1=check(intIn1,intT);
intS2=check(intIn2,intT-1);
if (intIn1%intT!=0 || intIn2%(intT-1)!=0)
continue;
if (intS2==intS1)
{
intA1=intT;
intA2=intT-1;
break;
}
}
intSum=0;
for (intT=0 ;intT<intS1 ;intT++)
intSum+=(int)pow(intA2,intT);
cout << intSum << " ";
intSum=0;
for (intT=0 ;intT<=intS1 ;intT++)
intSum+=(int)pow(intA1,intT)*(int)pow(intA2,intS1-intT);
cout << intSum << endl;
}
return 0;
}[/cpp]
```

but maybe you can test your program with this:

Code: Select all

```
input:
371293 248832
11 10
1 1
1048576 59049
1 14
1 0
0 0
output:
22621 1840825
1 21
0 1
29524 4017157
0 14
0 0
```