107 - The Cat in the Hat

[lorderico]

This, is why uva problems can be frustrating. To me:

The number of cats inside each (non-smallest) cat's hat is a constant, N. The height of these cats-in-a-hat is 1/(n+1) times the height of the cat whose hat they are in.

The smallest cats are of height one;
these are the cats that get the work done.

All heights are positive integers.

Clearly implies that any values of N which results in non-integer heights are not allowed. For instance:
5 1 with a solution of 2 8 would not be valid because 5 is prime so nothing divides into it (ex: N=1, 5/(n+1)=5/2, 2.5/2 =1.25). In this case N would have to be 4, but this would result in 4 worker cats....
That they expect you to round is not obvious.

Eric

[smpss91148]

Please help me find out where the problem is. (I think that maybe it is because of log(). )

Code: Select all

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

int main(void)
{
   int H,Nof1;
   int i,j,noworkN,allH,nowN;
   double temp;
   while(1)
   {
      scanf("%d %d",&H,&Nof1);
      if(!H && !Nof1)
         return 0;
      else
      {
         if(Nof1<=1)
         {
            i=1;
            j=2;
         }
         else
         {
            for(i=(int)round(sqrt(Nof1));i>1;i--)
               if(!(Nof1%i))
               {
                  temp=log(Nof1)/log(i);
                  if(fabs(round(temp)-temp)<0.001)
                  {
                     j=i+1;
                     temp=log(H)/log(j);
                     if(fabs(round(temp)-temp)<0.001)
                        break;
                  }
               }
            if(i==1)
            {
               i=Nof1;
               j=i+1;
            }
         }
         noworkN=0;
         allH=0;
         nowN=1;
         while(H>1)
         {
            noworkN+=nowN;
            allH+=(nowN*H);
            H/=j;
            nowN*=i;
         }
         allH+=nowN;
         printf("%d %d\n",noworkN,allH);
      }
   }
}

[brianfry713]

I solved this without using doubles, log, round, or sqrt, only integers.

[Marcgal]

@kbr_iut,
my AC code for ur input gives this:
Input:

Code: Select all

2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
0 0

Ouptut

Code: Select all

1 3
2 5
2 7
SIGXCPU

To me, ouptut 1 4 for input 3 1 makes no sense (as well as any other output)! First, the smallest cat must always be at height 1, which is clearly stated. Only one not working cat suggests that the whole stack has only two cats; but then you say that the stack has height 4. This would mean that the first cat has height 3 and the second height 1, while it should have height 3*(1/(1+1))=3/2 instead. 3/2 rounds to 2, not 1.

Because my AC code gave SIGXCPU/other answers for most of ur input I think that ur input is incorrect.

Input

Code: Select all

2 1
4 1
8 1
0 0

is, however, worth considering. It is completely correct. It should have

Output

Code: Select all

1 3
2 7
3 15

[brianfry713]

My AC code agrees with kbr_iut. Integer division is rounded down.

[kozlo]

Here are test cases which helped me to get AC. Hope that helps somebody.
Input:

Code: Select all

216 125
5764801 1679616
49 36
343 216
16 1
1 1
3 2
4 3
0 0

Output:

Code: Select all

31 671
335923 30275911
7 127
43 1105
4 31
0 1
1 5
1 7

Konrad

[axelblaze]

I'm getting time limit... don't know if it's WA or not...tested all the inputs possible...
Here's my code...

Code: Select all

#include<iostream>
#include<cmath>
using namespace std;

int main()
{
    unsigned long long h1,nums,ans1,ans2;
    double level,temp;
    int i;
    bool flag;
    while(cin>>h1>>nums,h1||nums)
    {
        flag=false;
        for(i=1;i<=h1;i++)
        {
            level=log(nums)/log(i)+1;
            if(ceil(level)==floor(level))            //to check if level is a whole number
            {
                //cout<<i<<" ";
                if(h1==pow((i+1),level-1))
                {
                    flag=true;
                }
                /*else if(i==1)
                {
                    temp=log(h1)/log(2);
                    if(ceil(temp)==floor(temp))
                        flag=true;
                }*/
            }
            if(flag)break;
        }
        if(flag==false)
        {
            level=log(h1)/log(2)+1;
            //cout<<"Level: "<<level<<endl;
            ans1=level-1;
            i=1;
        }
        else
        {
            ans1=abs(pow(i,level-1)-1)/abs(i-1);
        }
        ans2=0;
        for(int a=1,b=level;a<=level;a++,b--)
        {
            ans2+=(pow(i+1,b-1))*(pow(i,a-1));
        }
        cout<<ans1<<" "<<ans2<<endl;
    }
    return 0;
}

[brianfry713]

scanf and printf are faster than cin and cout.

Try solving it without using floating point.

[machoney]

Hello, i just made an AC with this problem and want to give few tips to others.

The main hardship in this problem is a horrible input/output example code, also those provided in this thread are mostly misguiding and wrong, so after a lot of pain and failure attempts by making some random corrections i eventually collected proper input and gathered enought data to finish the algorithm...

Input:

11 10
81 64
5764801 1679616
1 1
2 1
4 1
216 125
125 64
1024 243
371293 248832
1024 1
64 1
1048576 59049
483736625 481890304
0 0

Output:

1 21
9 217
335923 30275911
0 1
1 3
2 7
31 671
21 369
121 3367
22621 1840825
10 2047
6 127
29524 4017157
615441 1931252289

I will try to point out important things to pay attention to:
- since the range of values is undefined i decided to play it safe and used double type of variables,

fprintf(stdout,"%.0lf %.0lf\n",total_idlers,stack_height);

This line generates correct output, just in case someone was wondering if maybe the presence of '\n' in the last line might be the reason of WA

- Instead of making one generic algorithm, try to exclude special cases like:
if (initial_height==workers+1),
if (workers==1), this has two cases, one is when initial height divides by 2 down to 1, (all multipliers of 2) and when it doesnt (eg. 10) in which case i simply print : total_idlers=1; stack_height=initial_height+1;
there is no logic in last case but the debugger seems to like it that way ;D

Now, for the rest of the cases, you are looking for the "divider", when you have it you print the answer and this is where you fail miserably, then start hopelessly banging your head against the wall *,..,*

The reason is that some numbers have several 'working' dividers, and before you move on you have to verify it and if it wont work then for look for another
Basically the initial height and workers should divide exact amount of times by the 'divider' before reaching 1.

I hope that it will be helpfull and that i didint spoilered too much