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

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

Questioning input...

Post by rbuchan » Fri Feb 28, 2003 8:22 am

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

Post by rbuchan » Fri Feb 28, 2003 8:31 am

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:

...

Post by rbuchan » Fri Feb 28, 2003 9:45 am

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

Post by rbuchan » Fri Feb 28, 2003 2:50 pm

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. :oops:

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

TLE

Post by rbuchan » Fri Feb 28, 2003 2:57 pm

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! :wink:

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Fri Feb 28, 2003 11:57 pm

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:

Post by rbuchan » Sat Mar 01, 2003 4:02 am

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

Post by rbuchan » Sat Mar 01, 2003 4:11 am

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. :cry: [/cpp]

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

Ignore my previous posts...

Post by rbuchan » Sat Mar 01, 2003 7:45 am

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

:evil: Windows :evil:

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:

Post by yiuyuho » Sun Mar 02, 2003 7:13 am

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

Post by rbuchan » Sun Mar 02, 2003 7:42 am

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
New poster
Posts: 11
Joined: Sat Mar 08, 2003 3:46 pm

107 WA

Post by de » Sun Mar 16, 2003 10:14 am

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]

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

Post by shamim » Sun Mar 16, 2003 11:42 am

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
New poster
Posts: 11
Joined: Sat Mar 08, 2003 3:46 pm

Post by de » Sun Mar 16, 2003 4:02 pm

are the correct answers 3 15 and 4 31?

I have fix the problem but still got WA :cry:

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Sun Mar 16, 2003 5:10 pm

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 :D

Post Reply

Return to “Volume 1 (100-199)”