10493  Cats, with or without Hats
Moderator: Board moderators

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

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
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?
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?
What's the problem with this code??
Can anyone tell me whats the problem with the following code?
Why it gets WA??
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);
}
}
}

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
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);
}
}
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=(nm1)/(n1).
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.
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=(nm1)/(n1).
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.

 Experienced poster
 Posts: 147
 Joined: Mon Jun 07, 2010 11:43 am
 Location: University Of Dhaka,Bangladesh
 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=(MN)/(N1), 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+(T1)*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.
happy programming
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=(MN)/(N1), 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+(T1)*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
UVa stats: http://felixhalim.net/uva/hunting.php?id=63448
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
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.
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