SPOJ.com - Problem MECGROUP

MECGROUP - project groups

HOD of CSE Dept. of MMMEC, asked the students to form the groups for their final year project. He said that there will be t students per team and there will be at least 4 boys and at least 1 girl per group.

A curious student Rajesh want to know the total number of ways by which the groups can be made. Because he is busy in forming his group so you, write a program to find the total ways and help him.

Input

First line contains an integer n which itself indicates number of test cases.

Each test case comprises of three space separated integers "B G t". Where B denotes number of boys, G denotes number of girls in the class, and t denotes number of students in a group.

Constraints

1 <= n <= 20

4 <= B <= 30

1 <= G <= 30

5 <= t <= B + G

Output

For each test case print total number of ways per line.

Example

Input:
2
4 1 5
30 30 20

Output:
1
4191318957352590

Submit solution!

Added by:	bristy
Date:	2012-01-10
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ADA95 ASM32 ASM64 GAWK BASH BF CLPS CLOJURE LISP sbcl LISP clisp D ERL FSHARP FORTRAN GO HASK ICON ICK JS-RHINO LUA NEM NICE OCAML PERL PERL6 PHP PIKE PRLG-swi RUBY SCALA SCM guile SCM qobi SED ST TCL WHITESPACE
Resource:	own

hide comments

2015-02-05 15:24:30 Chetan
A Simple PnC Problem made difficult because of Unclear Language! Finally AC! :D

2013-05-06 19:27:50 Federico LebrÃ³n
As clarification, when the author writes "for B=5,G=1 & T=5 there will be only 1 group", he does not mean that the answer for "5 1 5" is 1, he is speaking about something else.

The answer for "5 1 5" is 5.

2013-04-08 22:19:00 D Pratap
Thank you Triveni Mahatha ..
Author please change the statement .. program need to compute how many ways t students(including at least 1 girl and at least 4 boys) can be selected from given class

2013-01-07 16:55:22 triveni
Problem statement should be something like that: there are B boys and G girls .
In how many ways one can select a group of t students in which there is atleast
4 Boys and atleast 1 Girl..
At least I got accepted with this assumption only..
:)

2012-02-25 00:00:28 Mitch Schwartz
@zukow aka :D
Thanks so much! Now I finally understood what the author meant to ask. Agreed, the wording should be fixed.

2012-02-24 23:17:19 :D
bristy, you REALLY need to clarify the description. As it is now it seems that we need to find the number of ways to split the whole students pack into groups, but in reality we are looking for number of different SINGLE groups.

2012-02-23 18:44:50 bristy
if (B+G)%t!=0 then remaining students will not be in any group.
for B=5,G=1 & T=5 there will be only 1 group.

2012-02-23 18:17:56 Mitch Schwartz
I strongly suspect that the only way to get AC is through a wrong method.

My calculations (see previous comments) are supported by, for example, https://oeis.org/A200472 . Reiterating a little: For (B,G,t)=(30,30,20) and ignoring "at least 4 boys, at least 1 girl", we are simply counting the number of ways to divide 60 people into 3 equal-sized groups. It's either x=96305202413079303971977650 or 3!*x depending on whether you label groups. It's not a hard problem in combinatorics, and my forum post gives an alternative way to calculate. Adding on the restriction "at least 4 boys, at least 1 girl" can't possibly reduce the count to 4191318957352590 -- that's way too low.

Also, Leppy's question is good; why didn't anyone answer it? I would assume that when (B+G)%t!=0 the answer is 0, because the requirements can't be met.

Anyway: Please either fix/remove the problem, or point out my mistake. Thanks.

2012-02-23 18:17:56 LeppyR64
Can we assume that (B+G)%t==0? Or if (B+G)%t!=0 what to do with the extra?

Last edit: 2012-01-18 01:54:48

2012-02-23 18:17:56 Mitch Schwartz
Someone who got AC, or problem setter, please let me know why my approach is wrong. (See my previous comment, and forum link.) I think my concerns should not be hard to address.