
ZOJ Problem Set  1820
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. 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.
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.
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.
8
8 Source: Greater New York 2003 