Problem B
n Group k
Input: Standard Input
Output: Standard Output
Time Limit: 3 Seconds
The good thing about X's students is that they do not have any preference or any objection about the groups that the professor would form. But that is actually the problem for the professor: he has got too many options open for him. Your task would be to aid the professor in two types of query:
Let
A be a possible solution, then A would be a set of Ceiling(n/k) groups. One
student can be a member of exactly one group in A. And you should also notice
that two different placement orders of the same students in a group are
considered to be the same. In other words, the task is about generating the set
of all possible A's or to count how many A's are possible.
Input
Output
For each of the "COUNT" queries, output an integer in one line giving the total number of solutions. You can assume that the output will always fit in a 64bit unsigned integer. For each of the "GENERATE" queries, output the total number of solutions, followed by that many number of lines. In each of those lines you are to print the groups. The professor has assigned the first N letters (uppercase) of the english alphabet to his N students. In each group the students are to be listed in alphabetic order and all the groups in a solution are to be sorted in ascending order. You have to use a single space to separate two groups in a solution. The solutions themselves have to be sorted in lexicographic order (to be more specific, you can use the ASCII values to do the comparison). Because of the sorting criterion the output will always be unique. You can assume that the number of solutions printed for each of the "GENERATE" queries will not be more than 10000 lines and collectively the solutions printed for all the "GENERATE" queries will not be more than 30000 lines.
COUNT 4 2 GENERATE 4 3 END
|
3 4 A BCD ABC D ABD C
ACD
B |
Problemsetter: Monirul Hasan, Member of Elite Problemsetters' Panel
Special thanks to Derek Kisman
"What was lost was found; what was found was never lost."