Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

Language:
Fully Diversified Sequences of Sets
 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 468 Accepted: 239 Special Judge

Description

Given a positive integer n, let N be the set of integers from 1 to n. A finite sequence A1, ..., Ak of subsets of N is fully diversified if:
a. Each subset Ai has an even number of elements.
b. For each element m in N, there are exactly m sets Ai in the sequence with m as a member.
For example, the sequence of subsets {1,3}, {2,3}, {2,3} is a fully diversified sequence of subsets of {1,2,3}. (Note that subsets in the sequence may be the same.)
A fully diversified sequence of subsets of N is minimal if no other fully diversified sequence of subsets of N has a smaller sequence count. The example above is minimal since the element 3 must occur in 3 different sets.
Write a program, which, given an integer n, determines whether there is a fully diversified sequence of subsets of the corresponding set N and, if there is a fully diversified sequence, finds a minimal fully diversified sequence of subsets of N.

Input

The input will be a sequence of positive integers n, one per line followed by a zero (0) (on another line) indicating the end of the input.

Output

If there is no fully diversified sequence of subsets of the corresponding set N, output a 0 on one line followed by a blank line.
If there is a fully diversified sequence of subsets of the corresponding set N, output the number of sets in your minimal sequence on one line, followed by the sets, one per line, followed by a blank line.
The elements of each set should be output in increasing order with a single space between numbers. The sets of sequences should be output in lexicographical order. There may be many possible solutions to each problem.

Sample Input

```8
9
11
17
23
0```

Sample Output

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

0

11
1 5 7 8 9 11
2 5 7 8 10 11
2 5 7 8 10 11
3 5 7 9 10 11
3 6 7 9 10 11
3 6 7 9 10 11
4 6 8 9 10 11
4 6 8 9 10 11
4 6 8 9 10 11
4 6 8 9 10 11
5 7 8 9 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```

Source

[Submit]   [Go Back]   [Status]   [Discuss]