107 - The Cat in the Hat

[Ivor]

I won't argue with you. The only thing I want to say is that you won't improve the time much. I doubt that it is possible to solve this problem without using logarithms/exponentiations/sums or that kind a stuff -- they are all iterative and will depend on some variable... it still won't be O(1) solution although it won't be visible in the code itself. And FPU is not the fastest thing I've seen.

I hope you will be able to find some solution -- I'd very much like to see it. I never turn down any possible good approach.

Best regards
Ivor

[razibcse]

I m gettin WA for this program, but it seems to give correct result..

someone pls help me with the input file or suggestions...

Code: Select all

#include <stdio.h>
#include <math.h>

void main()
{
long n,n2,m,level,a,flag;
double temp,height_of_stack,num_of_worker;
double height_of_first,non_working;
float rev,n1;

for(;;)
{
scanf("%lf %lf",&height_of_first,&num_of_worker);
if(height_of_first==0 && num_of_worker==0)
  break;

if((height_of_first-num_of_worker)==1.0)
   printf("%ld %.0lf\n",1,(height_of_first+num_of_worker));
else
 {
flag=1;
for(m=2;m<=31;m++)
 {
 rev=1.0/m;

 n1=pow(num_of_worker,rev);
 n2=(long)n1;

 if((n1-n2)<1.0)
   {
   if(height_of_first==pow((double)(n2+1),m))
      {
      n=n2;
      level=m;
      flag=0;
      }
   }
  if(!flag) break;

 }

 temp=n-1;

 non_working=(num_of_worker-1)/temp;
 height_of_stack=0;

 for((a=0,m=level);a<=level;(a++,m--))
   height_of_stack+=(pow((double)n,a)*pow((double)(n+1),m));

 printf("%.0lf %.0lf\n",non_working,height_of_stack);
 }
}
}

[yiuyuho]

I dunno what exactly is wrong in the code, but I can tell you that a input set:
1 1
should give:
0 1
while yours give 0 30275911

.
Hope it helps

[yiuyuho]

something else
you program 7776 16807 ->3361 30275911

should be 1555 70993

[R]

are you sure about that 7776 16807 example?

i don't think this is a valid input sequence.
16807 would make you think of N=7 (actually, what is N in your case?) but then the initial height of the first cat is 32768 and the other numbers are also different.

you can't take arbitrary integers for the input sequence. they have to describe a valid tree.

or am i getting something wrong?

[yiuyuho]

sorry,
should be 16807 7776
and your output is close but has a little bit error.

Good Catch, by the way

[Bor-Yeh Shen]

i think i have solved problem 107, but i still get WA.

can any preson help me?...thanks a lot.

[c]
#include <stdio.h>

int
level(int num, int div)
{
int tmp = num;

while (tmp % div == 0)
{
tmp /= div;
}
return tmp;
}

main()
{
int tall, num, tmp;
int i, j, k;
int sum, sumtall;

while (scanf("%d %d", &tall, &num) == 2 && (tall | num))
{
if (num != 1)
for (i = 2; i < num; i++)
{
if (level(num, i) == 1) break;
}
else
i = num;

for (j = 0, sum = 0, tmp = num;; j++)
{
if (tmp == 1) break;
else
{
tmp /= i;
sum += tmp;
}
}

for (k = 1, sumtall = 0; k < tall; k *= i + 1)
{
if (i == 1) sum++;
sumtall += k;
sumtall *= i;
}
sumtall += tall;

printf("%d %d\n", sum, sumtall);
}
}

[/c]

[joecrow]

I am getting a wrong answer as well. when I use the suggested input of 16807 and 7776, I get back 1555 and 70993. When I work out the problem by hand, these seem to be the correct numbers. So what I'm asking is my algorithm incorrect or are the numbers posted earlier incorrect?

thanks

[yiuyuho]

I am very sorry, I make a mistake on the previous example.

[yiuyuho]

390625, 65536 -> 21845 1690981

Good Luck!

[Sneeze]

I have tried lots of inputs (partly from the Problemset Archive and partly from some discussions about q107) by hand and it always gave me right answers. I can't figure out why I should get "float point exception."

The followings are the considered most "fragile" part in my code. I hope someone can help me.

[cpp]
if(pow((t_base+1), t_count)==o_height)
{
test=0;
cout << (w_cats-1)/(t_base-1) << " "
<< long(o_height*(t_base+1)-pow(((long double)t_base/(t_base+1)), t_count)*o_height*t_base) << endl;
/*Be careful!! Math+Precision*/
}
[/cpp]

This is part of the "output" part of my program.
<all the above-mentioned are declared as "long">

[Adrian Kuegel]

are you sure that t_base is always != 1?
if it is 1, you will get a floating point exception (note that this happens if you divide by integer 0).

[Sneeze]

I'm sure I've prevented "t_base" from being 1, since before this part I have an "if" to handle the problem directly when there is only ONE working cat. For example, when I input "64 1", I will get "6 127", right answer, isn't it? Or did I ignored any other "except" situations?

[bgsufalcon1]

I have submitted my answer several times, and I keep getting wrong answers. However, in these last cases, I have to disagree because my algorithm is mathematically sound. I also got a hold of old test data from the actual contest this was used in, and my output matches that output. Unfortunately, I still get WA. I have tested my answer for about as many solutions as it should take, including border cases.

Any help would be appreciated.

[rbuchan]

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

void findTheRoot();
bool checkForAMatch(long);
long findPower(long);

long bigCatHeight = 1;
long workerCats = 1;
long theTotalCats = 0;
long theRoot = 0;
long thePower = 0;
long theLazyCats = 0;
double theStackHeight = 0;

int main()
{
while (true) {
cin >> bigCatHeight >> workerCats;
if (bigCatHeight == 0) break;

theRoot = 0;
thePower = 1;
theLazyCats = 0;
theStackHeight = 0;

if (workerCats == 1) {
theLazyCats = 0;
}
else {
findTheRoot();
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));
cout << setiosflags(ios::fixed) << setprecision(0);
cout << theLazyCats << " " << theStackHeight << endl;
}
return 0;
}

void findTheRoot() {
for (int j = 2; j <= workerCats; j++) {
if (checkForAMatch(j)) {
theRoot = j;
break;
}
}
}

bool checkForAMatch(long t) {
long k = findPower(t);
return ((k != 0) && (pow(t+1, k) == bigCatHeight));
}

long findPower(long n) {
long pwr = 0;
long b = workerCats;
while (b % n == 0) {
pwr++;
b = b / n;
if (b == 1) {
thePower = pwr;
return pwr;
}
}
return 0;
}[/cpp]