描述

给定一个正整数 (n)，令 (N) 为从 (1) 到 (n) 的整数集合。有限子集序列 (A_1, \cdots, A_k) 满足以下条件时被称为完全多样化序列： a. 每个子集 (A_i) 都包含偶数个元素。 b. 对于 (N) 中的每个元素 (m)，在该序列中恰好有 (m) 个集合 (A_i) 包含 (m) 作为其成员。

例如，子集序列 ({1,3})，({2,3})，({2,3}) 是集合 ({1,2,3}) 的一个完全多样化序列。（注意，序列中的子集可能是相同的。）

如果不存在其他集合 (N) 的完全多样化序列，其序列元素数量比某个完全多样化序列更少，那么这个集合 (N) 的完全多样化序列就被称为最小完全多样化序列。上述例子是最小的，因为元素 (3) 必须出现在 (3) 个不同的集合中。

编写一个程序，对于给定的整数 (n)，判断是否存在对应的集合 (N) 的完全多样化序列，如果存在完全多样化序列，则找到集合 (N) 的一个最小完全多样化序列。

输入

输入将是一个正整数 (n) 的序列，每行一个，随后在另一行输入一个 (0) 表示输入结束。

输出

如果不存在对应的集合 (N) 的完全多样化序列，则在一行中输出一个 (0)，后面跟一个空行。

如果存在对应的集合 (N) 的完全多样化序列，则在一行中输出你找到的最小序列中的集合数量，然后每行输出一个集合，之后跟一个空行。

每个集合的元素应以升序输出，数字之间用单个空格分隔。序列中的集合应以字典序输出。每个问题可能有许多可能的解决方案。

输入数据 1

8
9
11
17
23
0

输出数据 1

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

题目来源

大纽约地区 2003 年竞赛

C++实现

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <functional>
#include <map>
#include <string.h>
#include <math.h>
#include <list>
#include <set>
using namespace std;
 
int N;
vector<vector<int> > v;
 
void output() {
    cout << N << endl;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < v[i].size(); j++) {
            if (j) cout << " ";
            cout << v[i][j];
        }
        cout << endl;
    }
    cout << endl;
}
 
int main() {
 
    std::ios::sync_with_stdio(false);
 
    while (1) {
        cin >> N;
        if (!N) break;
        if (((1 + N) * N / 2) % 2 == 1) {
            cout << 0 << endl << endl;
            continue;
        }
        v.clear();
        v.resize(N);
        int put;
        int vSize;
        if (N % 2) {
            put = 3;
            vSize = -1;
        } else {
            put = 4;
            vSize = 0;   
        }
        while (put <= N) {
            for (int i = 0; i <= vSize; i++) {
                v[i].push_back(put - 3);
                v[i].push_back(put - 2);
                v[i].push_back(put - 1);
                v[i].push_back(put);
            }
            v[vSize + 1].push_back(put - 2); v[vSize + 1].push_back(put);
            v[vSize + 2].push_back(put - 1); v[vSize + 2].push_back(put);
            v[vSize + 3].push_back(put - 1); v[vSize + 3].push_back(put);
            vSize += 4;
            put += 4;
        }
        output();
    }
 
    return 0;
}