## 107 - The Cat in the Hat

Moderator: Board moderators

lorderico
New poster
Posts: 6
Joined: Sat Oct 02, 2010 10:47 pm

### Re: WA in 107

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
New poster
Posts: 3
Joined: Mon Jul 23, 2012 4:51 pm

### No.107 I got Runtime error

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);
}
}
}
``````
Last edited by smpss91148 on Tue Jul 31, 2012 10:21 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: No.107 I got Runtime error

I solved this without using doubles, log, round, or sqrt, only integers.
Check input and AC output for thousands of problems on uDebug!

Marcgal
New poster
Posts: 3
Joined: Tue Jul 02, 2013 6:19 pm

### Re: WA in 107

@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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: WA in 107

My AC code agrees with kbr_iut. Integer division is rounded down.
Check input and AC output for thousands of problems on uDebug!

kozlo
New poster
Posts: 1
Joined: Mon Jan 06, 2014 8:18 pm

### Re: WA in 107

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

axelblaze
New poster
Posts: 34
Joined: Mon Jun 23, 2014 7:45 pm

### Re: 107 - The Cat in the Hat

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 107 - The Cat in the Hat

scanf and printf are faster than cin and cout.

Try solving it without using floating point.
Check input and AC output for thousands of problems on uDebug!

machoney
New poster
Posts: 1
Joined: Tue Sep 22, 2015 11:27 pm

### Re: 107 - The Cat in the Hat

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 