10493 - Cats, with or without Hats

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10493 - Cats, with or without Hats

Post by Red Scorpion »

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:

Post by Pier »

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

Post by Red Scorpion »

Oh,,, thanks. I got it. :lol: :lol: :lol: :lol:

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

WA again and again : 10493 Cat ...

Post by laboni »

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

Post by laboni »

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

Post by Red Scorpion »

for n = 2, and m = 1.
the solution is "2 1 1" not "impossible".

:lol: :lol: :lol:

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

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. :oops:
"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

Post by sunnycare »

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:

Post by mf »

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

Post by sunnycare »

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:

Post by mf »

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
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

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
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10493 - Cats, with or without Hats

Post by Shafaet_du »

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

Post by plamplam »

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. :lol:
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

Post Reply

Return to “Volume 104 (10400-10499)”