PKU 2245. Lotto.

복권

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 3799	Accepted: 2458

설명

독일식 복권은 {1,2,...,49} 중 6개의 숫자를 고릅니다. 비록 당첨확률을 높여주는 방법은 아니지만, 대중적인 선택방법에는, 49개의 숫자들 중 어떤 수 k (k > 6)를 포함하는 부분집합 S를 선택하여 그 안에서 숫자들을 고르는 것입니다. 예를 들어 k=8 이고 S = {1,2,3,5,8,13,21,34} 라면 [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] 등 가능한 선택하는 방법은 28개가 되겠습니다.

당신은 이제 k 와 집합 S를 받으면, S 안에서 가능한 모든 선택방법의 수를 고르는 프로그램을 작성하세요.

입력

입력은 하나 또는 그 이상의 테스트 케이스들로 이루어집니다. 각 테스트 케이스는 여러 정수들로 이루어져있는데, 각 정수 사이에는 공백을 둡니다. 각 줄의 첫번째 정수는 k (6 < k < 13) 이고, k개의 정수가 뒤이어 나오는데, 오름차순으로 S의 원소를 전부 나타냅니다. 입력은 k 위치에 0 을 넣으면 종료되도록 합니다.

출력

각 테스트 케이스에 대해, 가능한 모든 방법의 수를 한 줄에 나타냅니다. 각 방법에 쓰일 수들은 오름차순으로 정리되어야 하고, 각 숫자 사이엔 공백을 둡니다. 각 방법들은 사전식으로, 다시 말하면 가장 작은 숫자로 시작하는 방법이 처음에 나오고, 그 다음으로 작은 숫자로 시작하는 방법 순으로 가서, 밑에 나오는 출력 예시처럼 나오게 합니다. 각 테스트 케이스들은 비어있는 하나의 줄로 분리시켜둡니다. 마지막 테스트 케이스 뒤에는 빈 줄을 넣지 마세요.

입력 예시

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

Source

Ulm Local 1996