Bytelandian ShoppersProblem code: BYTESHOP |
All submissions for this problem are available.
There are N shoppers today at the Bytelandian Shopping Mall. There are M different items at sale at the mall. In how many ways can shoppers purchase R items in all such that everyone buys atleast one item, and every item is brought by atleast one person ? A shopper can purchase any particular item at most once.
Input : The first line contains the number of test cases T. T lines follow containing 3 integers: N,M and R. (1 <= T <= 100. 1 <= N,M <= 200. 1 <= R <= N * M)
Output : Output T lines, one for each test case, containing the output for the corresponding test case. Output all values modulo 1000000007
Sample Input : 3 1 1 1 2 1 1 2 3 3
Sample Output : 1 0 6
| Date: | 2010-08-19 |
| Time limit: | 1s |
| Source limit: | 50000 |
| Languages: | C C99 strict C++ 4.0.0-8 C++ 4.3.2 PAS gpc PAS fpc JAVA NICE JAR C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK JS |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
A nice combinatorial problem!
A nice combinatorial problem!
:D:D:D
:D:D:D
what does the line Output
what does the line
http://en.wikipedia.org/wiki/
http://en.wikipedia.org/wiki/Modulo_operation
hi! can anybody give the
hi! can anybody give the complexity of this problem.
i have thought of a N^3 solution. which i think will time out.
i just want to be sure if there exists a (N^2 lg N) solution or we need to optimize N^3 solution.
@ashish: You are not allowed
@ashish: You are not allowed to discuss the complexity of the solution during the contest. Complexity hints at the solution and this is against the rules of the contest.
"every item is brought by
"every item is brought by atleast one person".How can one single item be bought by more than one person simultaneously?Does it mean that there is an infinite number of items of each type;differnt users buy differents copies of item of same kind?In that case "There are M different items" should mean that there are M kinds of items.
@ishan dutta As far as I
@ishan dutta
As far as I understand, there are M types of items at sale.
"every item is brought by atleast one person" means that at least one instance of every type must be sold.
"A shopper can purchase any particular item at most once." means that every buyer will by at most one instance of every item type.
I hope somebody will corect if this interpretation is wrong.
And "purchase R items" means
And "purchase R items" means purchase R instances of items.
everything is right than why
everything is right than why runtime error is coming.......
@Mohit If you get a runtime
@Mohit If you get a runtime error, then that means that everything is not right
@Burdakov Daniel. I
@Burdakov Daniel. I understand what the problem tries to mean but the language the writer wrote it in makes thinks unclear.No where in the problem statement the phrase "type of item" or "kind of item" is used. it just vagely refers R as well as M as the number of items.
Please Do give some more
Please Do give some more input/output samples becoz it is very difficult to trace problem in our program when it is running fine on our computer..............but not on your compiler
That's why this is a contest.
That's why this is a contest. You're expected to do the hard work, not other people.
A very crisp & beautiful
A very crisp & beautiful problem :)
From editorial: "The final
From editorial: "The final answer is given by summing G(i,j) over all (i,j). We add G(i,j) to the answer if (i + j) is even, else we subtract it."
Can someone please explain why this works?