[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
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.7ms with 1 query(s).