107 - The Cat in the Hat

[rbuchan]

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]

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

Hope this helps.

Ron

[rbuchan]

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]

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]

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]

It should be 390625, 65536 -> 21845 1690981,
sorry
7776 3125 -> 781 31031
14641 10000 -> 1111 61051

[rbuchan]

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]

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]

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]

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]

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.

[de]

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]

your program gives incorrect output for the following test cases.

8 1
16 1

your program gives:

1 0
1 0

this is incorrect.

[de]

are the correct answers 3 15 and 4 31?

I have fix the problem but still got WA

[Hisoka]

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