시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 16 8 4 44.444%

문제

양의 정수 n이 주어질 때 N을 1부터 n까지의 정수의 집합이라 하자. N의 부분집합의 수열 A1, …, Ak이 아래의 성질을 만족할 때 완전히 다양화 되었다고(fully diversified) 한다.

a. 각각의 부분집합 Ai가 짝수 개의 원소로 이루어 졌다.

b. 어떤 N의 원소 m에 대해 m을 원소로 갖는 Ai가 m개 존재한다.

예를 들어 {1, 2, 3}의 부분집합으로 이뤄진 수열 {1, 3}, {2, 3}, {2, 3}은 완전히 다양화 된 수열이다. (수열의 항은 같을 수 있다)

N의 부분집합의 수열 중 완전히 다양화 된 수열은 여러 개가 존재하는데, 그 중 가장 짧은 것을 최소라 한다. 위의 예는 3이 세 개의 다른 집합에 나타나야 하므로, 위 수열이 최소이다.

정수 n이 주어졌을 때, 완전히 다양화된 수열이 있는가를 판별하고, 있다면 최소의 다양화된 수열을 찾아라.

입력

양의 정수 n이 한 줄에 하나씩 입력된다. 0이 입력되면 입력을 종료한다.

출력

집합 N에 대해 완전히 다양화 된 수열이 없다면 0을 출력하고 다음 줄에 빈 줄을 출력한다.

완전히 다양화 된 수열이 있다면, 수열의 길이를 출력하고 다음 줄에 집합을 출력한 뒤 다음 줄에 빈 줄을 출력한다.

각각의 원소는 오름차순으로 출력하여야 하며, 숫자들 사이에는 빈 칸을 하나씩 출력한다. 수열의 집합은 사전 순으로 출력하여야 한다. 각각의 문제에 대해 답은 여러 개가 있을 수 있다.

예제 입력

8
9
11
17
23
0

예제 출력

8
1 2 3 4 5 6 7 8
2 4 5 6 7 8
3 4 5 6 7 8
3 4 5 6 7 8
5 6 7 8
6 8
7 8
7 8

0

11
1 3 4 5 6 7 8 9 10 11
2 3 4 5 6 7 8 9 10 11
2 3 4 5 6 7 8 9 10 11
4 5 6 7 8 9 10 11
5 7 8 9 10 11
6 7 8 9 10 11
6 7 8 9 10 11
8 9 10 11
9 11
10 11
10 11

0

23
1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
9 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23
12 13 14 15 16 17 18 19 20 21 22 23
13 15 16 17 18 19 20 21 22 23
14 15 16 17 18 19 20 21 22 23
14 15 16 17 18 19 20 21 22 23
16 17 18 19 20 21 22 23
17 19 20 21 22 23
18 19 20 21 22 23
18 19 20 21 22 23
20 21 22 23
21 23
22 23
22 23

힌트