| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1380
组合
Time Limit: 1000ms
Memory Limit: 65536kb Description
在使用C++进行编程的时候，合理的使用STL既能加快编码速度，又能大大的提高代码的健壮性、可读性。举例来说，假设我们需要在程序中枚举1到n这n个整数的所有排列，那么可以将这n个数存储在数组中（如数组array），再循环调用STL algorithm中的next_combination，即可得到1到n所有可能的排列。 有关next_permutation的具体用法可参考C++文档，有关其实现的讨论可参考stackoverflow的讨论。 但在stl库algorithm中，并没有next_combination这样的函数。本题要完成的任务，就是编写一个next_combination，以实现枚举组合的功能。 对于一个长度n为4的序列0、1、2、3。其k等于2的组合排序为：0：0、1 1：0、2 2：1、2 3：0、3 4：1、3 5：2、3 冒号前的数字为该组合数的序号。 类似的，对于一个长度n为4的序列7、2、5、9。其k等于3的组合排序为： 0：7、2、5 ----> 0、1、2 1：7、2、9 ----> 0、1、3 2：7、5、9 ----> 0、2、3 3：2、5、9 ----> 1、2、3 注： 1，每一个“n选k”组合的元素由元素在原序列中的序号排序（序号小的在前，大的在后）。 2，对于两个组合，它们的比较规则如下。首先将这个组合转换为对应的序列，然后从右数第一位开始比较，大的排在后面；若相等，则比较右数第二位；如是往复。 Input
输入的第一行仅有一个整数t（0≤t≤10^5），表示测试数据的组数。接下来是t组测试数据。每组测试数据占两行。第一行包含三个整数n、k、p（2≤n≤200，1≤k≤200， 0≤p＜100）。第二行由n个两两不同的整数组成，每个整数i满足0≤i≤10^5。 Output
每组测试数据的输出占一行，按顺输出第p个n选k组合。该组合由k个整数构成，整数间以空格分开。最后一个整数后没有空格。
Sample Input
6 4 2 0 0 1 2 3 4 3 2 7 2 5 9 4 3 3 7 2 5 9 4 2 5 0 1 2 3 4 3 0 7 2 5 9 4 2 3 0 1 2 3 Sample Output
0 1 7 5 9 2 5 9 2 3 7 2 5 0 3 |