OpenJudge

03:Lotto

总时间限制:
1000ms
内存限制:
65536kB
描述
In the German Lotto you have to select 6 numbers from the set {1,2,...,49}. A popular strategy to play Lotto - although it doesn't increase your chance of winning - is to select a subset S containing k (k > 6) of these 49 numbers, and then play several games with choosing numbers only from S. For example, for k=8 and S = {1,2,3,5,8,13,21,34} there are 28 possible games: [1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ... [3,5,8,13,21,34].

Your job is to write a program that reads in the number k and the set S and then prints all possible games choosing numbers only from S.
输入
The input will contain one or more test cases. Each test case consists of one line containing several integers separated from each other by spaces. The first integer on the line will be the number k (6 < k < 13). Then k integers, specifying the set S, will follow in ascending order. Input will be terminated by a value of zero (0) for k.
输出
For each test case, print all possible games, each game on one line. The numbers of each game have to be sorted in ascending order and separated from each other by exactly one space. The games themselves have to be sorted lexicographically, that means sorted by the lowest number first, then by the second lowest and so on, as demonstrated in the sample output below. The test cases have to be separated from each other by exactly one blank line. Do not put a blank line after the last test case.
样例输入
7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0
样例输出
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34
来源
Ulm Local 1996

1、2图论中的遍历问题,也可用解答树分析递归遍历 数据结构类型书籍都有详细分析有关图论算法
3、10数字升序问题可用枚举加决策也可用回溯《算法竞赛经典入门》7.2中有详细介绍各种变种的数字排列
6、7是贪心算法的经典题型《算法的乐趣》中有对各个算法通俗易懂详细介绍的经典母题
8、用三种基础排序<插入排序,冒泡排序,选择排序>《数据结构》排序章节有三种算法复杂度的分析
5、最长递增子序列的变形题,递减形式可用NP<本次题型中都可用动态规划思想分析解决>《妙趣横生的算法C++》对动态规划有通俗的介绍的例题分析
八皇后问题可缩小为4皇后问题,可用递推,回溯等思想解决

全局题号
1247
添加于
2016-09-16
提交次数
9
尝试人数
3
通过人数
3