## 107 - The Cat in the Hat

Moderator: Board moderators

rbuchan
New poster
Posts: 27
Joined: Fri Feb 28, 2003 7:59 am
Contact:

### 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.

???

rbuchan
New poster
Posts: 27
Joined: Fri Feb 28, 2003 7:59 am
Contact:

### Suggestion...

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

Hope this helps.

Ron

rbuchan
New poster
Posts: 27
Joined: Fri Feb 28, 2003 7:59 am
Contact:

### ...

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???

rbuchan
New poster
Posts: 27
Joined: Fri Feb 28, 2003 7:59 am
Contact:

### 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.

rbuchan
New poster
Posts: 27
Joined: Fri Feb 28, 2003 7:59 am
Contact:

### 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!

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
It should be 390625, 65536 -> 21845 1690981,
sorry
7776 3125 -> 781 31031
14641 10000 -> 1111 61051

rbuchan
New poster
Posts: 27
Joined: Fri Feb 28, 2003 7:59 am
Contact:
Thanks for the reply and the correction. However, I ran the two other tests you gave me, and I get the correct answers for those as well, but the judge STILL says I have a "Wrong Answer".

rbuchan
New poster
Posts: 27
Joined: Fri Feb 28, 2003 7:59 am
Contact:

### [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]

rbuchan
New poster
Posts: 27
Joined: Fri Feb 28, 2003 7:59 am
Contact:

### 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.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
You probably did something else wrong,

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

rbuchan
New poster
Posts: 27
Joined: Fri Feb 28, 2003 7:59 am
Contact:

### 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.

de
New poster
Posts: 11
Joined: Sat Mar 08, 2003 3:46 pm

### 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]``````

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
your program gives incorrect output for the following test cases.

8 1
16 1

1 0
1 0

this is incorrect.

de
New poster
Posts: 11
Joined: Sat Mar 08, 2003 3:46 pm
are the correct answers 3 15 and 4 31?

I have fix the problem but still got WA

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
Yes, they are.
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``````
hope this will be help