Lotto
3678 ワード
Time Limit: 1 Seconds
Memory Limit: 32768KB
Problem Description
In a Lotto I have ever played, one has 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.
Input Specification
The input file 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.
Output Specification
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.
Sample Input
7 1 2 3 4 5 6 7 8 1 2 3 5 8 13 21 34 0
Sample Output
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 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
Problem Source
University of Ulm Local Contest 1996
【テーマ大意】
私がかつてプレイしたナンバープレートゲーム(楽透)では、プレイヤーは{1,2,...,49}から6つの数を選ばなければならない.Lottoをプレイする流行の戦略の一つは(勝つ機会を増やさないが):この49の数の中からk(k>6)の数を選んでサブセットSを構成し、Sからカードを取り出していくつかのゲームをプレイすることである.例えば:k=8,S={1,2,3,5,8,13,21,34}では28ゲーム:[1,2,3,5,8,21],[1,2,3,5,8,34],[1,2,3,5,3,5,...,[3,5,8,13,21,34].
【プログラミングタスク】
数字kと一組の数Sを読み出し、Sの中の数からなるすべての可能なゲームを出力する.
【入力形式】
テストデータのセットまたは複数のセットを入力します.テストデータのセットごとに1行ずつ、数と数の間にスペースで区切られます.行ごとの最初の整数はk(6)です.
【出力形式】
各テストデータのセットについて、可能なすべてのゲームを出力し、各ゲームが1行を占めます.ゲームには数字が昇順に並び、数と数の間にスペースがあります.すべてのゲームも辞書順に並べます.つまり、まず各ゲームの最初の数の大きさを比較し、次に2番目の数の大きさを順に類推します.以下の出力例に示します.異なるテスト例の間に空の行で区切られます.最後のテスト例のセットの後に空の行はありません.
【アルゴリズム解析】
本題では,1組の数から6個の数のすべてのゲームの組合せを選択し,各ゲームの数字を昇順に並べ,すべてのゲームを辞書順に並べ替えることを実現する.
実装されるアルゴリズムには,深さ優先探索などが含まれる.
しかし、最も簡単な方法はシミュレーションです.数字が整然としているので、行き先から選ぶと、昇順だけでなく辞書順になります.
0 1 2 3 ... n-6 n-5 n-4 n-3 n-2 n-1
順番に0~(n-6)番目の数字の間に1番目の数字を選び、順番はaである.2番目の数字は1番目の数字の順番aに1を加え、順番に数字を選び、n-5番目の数字まで選び、順番はbである.順番に類推する.
【説明補足】
①6つのforループの意味を理解し、forループの重ね合わせの効果と意味に注意する
Memory Limit: 32768KB
Problem Description
In a Lotto I have ever played, one has 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.
Input Specification
The input file 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.
Output Specification
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.
Sample Input
7 1 2 3 4 5 6 7 8 1 2 3 5 8 13 21 34 0
Sample Output
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 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
Problem Source
University of Ulm Local Contest 1996
【テーマ大意】
私がかつてプレイしたナンバープレートゲーム(楽透)では、プレイヤーは{1,2,...,49}から6つの数を選ばなければならない.Lottoをプレイする流行の戦略の一つは(勝つ機会を増やさないが):この49の数の中からk(k>6)の数を選んでサブセットSを構成し、Sからカードを取り出していくつかのゲームをプレイすることである.例えば:k=8,S={1,2,3,5,8,13,21,34}では28ゲーム:[1,2,3,5,8,21],[1,2,3,5,8,34],[1,2,3,5,3,5,...,[3,5,8,13,21,34].
【プログラミングタスク】
数字kと一組の数Sを読み出し、Sの中の数からなるすべての可能なゲームを出力する.
【入力形式】
テストデータのセットまたは複数のセットを入力します.テストデータのセットごとに1行ずつ、数と数の間にスペースで区切られます.行ごとの最初の整数はk(6)です.
【出力形式】
各テストデータのセットについて、可能なすべてのゲームを出力し、各ゲームが1行を占めます.ゲームには数字が昇順に並び、数と数の間にスペースがあります.すべてのゲームも辞書順に並べます.つまり、まず各ゲームの最初の数の大きさを比較し、次に2番目の数の大きさを順に類推します.以下の出力例に示します.異なるテスト例の間に空の行で区切られます.最後のテスト例のセットの後に空の行はありません.
【アルゴリズム解析】
本題では,1組の数から6個の数のすべてのゲームの組合せを選択し,各ゲームの数字を昇順に並べ,すべてのゲームを辞書順に並べ替えることを実現する.
実装されるアルゴリズムには,深さ優先探索などが含まれる.
しかし、最も簡単な方法はシミュレーションです.数字が整然としているので、行き先から選ぶと、昇順だけでなく辞書順になります.
0 1 2 3 ... n-6 n-5 n-4 n-3 n-2 n-1
順番に0~(n-6)番目の数字の間に1番目の数字を選び、順番はaである.2番目の数字は1番目の数字の順番aに1を加え、順番に数字を選び、n-5番目の数字まで選び、順番はbである.順番に類推する.
#include
int number[14]; //
int main(){
int line = 0; //
int n; //
while(scanf("%d",&n) && n){
if(line) printf("
");
for(int i=0; i 【説明補足】
①6つのforループの意味を理解し、forループの重ね合わせの効果と意味に注意する