## 10493 - Cats, with or without Hats

Moderator: Board moderators

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

### 10493 - Cats, with or without Hats

Hi, can anyone show me the condition when "multiple" is the answer.

Thanks.

Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:
I remember that it was when n=1 and m=1, but right now I can't remember exactly why...

If you have further trouble, I can re-think the problem and tell you why...
There are 10 kind of people on this world: those who understand binary and those who don't!

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
Oh,,, thanks. I got it.    laboni
New poster
Posts: 12
Joined: Sat Sep 14, 2002 9:22 pm
Location: India

### WA again and again : 10493 Cat ...

I am getting WA in this problem.
I found a formula in a discrete math book for this
and i used that one. I handled the case 1 1 specially as "multiple" and
"Impossible" if total number of node is fraction.
Can anyone help me with some special input/output?

laboni
New poster
Posts: 12
Joined: Sat Sep 14, 2002 9:22 pm
Location: India

### What's the problem with this code??

Can anyone tell me whats the problem with the following code?
Why it gets WA??

Code: Select all

``````[cpp][c]
/* 10493 : Cats, with or without Hats */
/* Discrete Math :Rosen -  page 536 */

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

void main()
{

long ary,leaf;
double total,fraction,integer;

while(scanf("%ld%ld",&ary,&leaf)==2 && (ary!=0 || leaf!=0))
{

printf("%ld %ld ",ary,leaf);
if(ary==1 && leaf==1) printf("Multiple\n");
else if(ary==1 && leaf > 1 )  printf("Impossible\n");
else if (leaf < ary )  printf("Impossible\n");
else
{
total = (1.0*ary*leaf - 1.0 )/ (ary - 1.0);
fraction = modf(total, &integer);
if(fraction!=0.0) printf("Impossible\n");
else if (total <= ary || total <= leaf)  printf("Impossible\n");
else printf("%.0lf\n",total);
}
}
}``````

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
for n = 2, and m = 1.
the solution is "2 1 1" not "impossible".   anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
i considered the graph as first a full m ary binary tree and then extendin some nodes and claculating the result.
and try to build a graph first,
then check the case when it has only 1 node, it has all node in a line. etc. "Everything should be made simple, but not always simpler"

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

### 10493 TLE

is my method wrong??

Code: Select all

``````//10493	Cats, with or without Hats
#include <cstdio>
using namespace std;

int main(int argc,char *argv[])
{
long n,m,s;
scanf("%d %d",&n,&m);

while(n!=0)
{
s=m;
printf("%d %d ",n,m);

while(m>=n)
{
s+=m/n;
m=m/n+m%n;
}
if(m==1)
{

printf("%d\n",s);

}
else
printf("Impossible\n");
scanf("%d %d",&n,&m);
}
}

``````

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Your program can enter infinite loop when n=1.

And there's a simpler O(1) solution.

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai
what method to solve it in O(1)

a math formula ??

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Suppose there are h cats with hats, each of which has n cats in its hat.
Then these h cats have in total nh cats in their hats.

Since each cat (except exactly one cat) is in some other cat's hat, it follows
that the total number of cats is: c = nh + 1.

But it is also known, that there are m cats without hats, and each cat
either has a hat or doesn't have it, so: c = m + h.

These two equations give a system in two unknowns (c and h):
c = nh + 1
c = m + h

Solving it, you obtain: c=(nm-1)/(n-1).

There are two special cases: if n=1, and m=1 there are infinitely many solutions, if n=1 and m != 1, there are no solutions.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
The general formula is (mn-1)/(n-1), just worry about the special cases.

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 10493 - Cats, with or without Hats

I loved this problem. My O(1) solution is a bit different than ones that mentioned above.
for n=2 the valid m are 1,2,3,4,5,6,7,8......
for n=3 the valid m are 1,3,5,7,9,11,13......
for n=4 the valid m are 1,4,7,10,13,16.......
you can see this pattern if you draw some trees in paper.
now for any of this series term T=(M-N)/(N-1), do a bit calculation to find the proof. If T is an integer than N is valid.
again for n=2 the answers can be 1,3,5,7,9,11.....
again for n=3 the answers can be 1,4,7,10,13,16...
now its clear that the answer is 1+(T-1)*N, you can prove it easily. so if M is valid we can find answer using this formula.

Take care of N=1 seperately, otherwise you will get wa or RTE.

Code: Select all

``````3 7
3 8
3 9
3 11``````

Code: Select all

``````3 7
3 8
3 9
3 11``````
happy programming plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 10493 - Cats, with or without Hats

Really amazing problem...although it took me some time to figure out the last special case, i.e, when n= 1 and m = 1. (I just tried harder because I couldn't find any test cases at first for which multiple solutions exist).
My solution is also a bit different. Yeah at first I drew some trees on paper and I also noticed that
for n=2 the valid m are 1,2,3,4,5,6,7,8......
for n=3 the valid m are 1,3,5,7,9,11,13......
(As Shafaet_du mentioned above). I therefore concluded (after handling the special test cases) if ( (m - 1) % (n - 1) == 0) Then total number of cats = (m - 1) / (n - 1) + m. Else it is impossible. You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson