問題概要

$1, 3, 5, \dots, 2N-1$ という $N$ 個の整数がある。これらを 2 個以上のグループに分ける。各グループの整数の総和が互いに等しくなるようにグループ分けすることが可能かどうかを判定し、可能ならば具体例を構築せよ。

制約

$2 \le N \le 10^{5}$

考えたこと

こういうのはいろんな $N$ で試していくのがよさそう。

$N = 2$ はダメ
$N = 3$ もダメ
$N = 4$ は (1, 7), (3, 5) で OK
$N = 5$ はダメ
$N = 6$ は (1, 11), (3, 9), (5, 7) で OK

この辺りでとりあえず

2 以外の偶数は OK
素数はダメ

といったことが見えてきた。2 以外の偶数は、(2i+1, 2N-2i-1) を並べれば OK。素数は、仮に可能だとすると、グループの個数を $M$ 、各グループの総和を $S$ とすると、

$N^{2} = SM$

となる。 $N$ は素数なので $M \ge 2$ だと $S = N$ 、 $M = N$ しかありえないけど、これもダメ。よって素数はダメ。

素数でない奇数のとき

多分いろんな方法があるけど、 $N = 3n$ と表せる場合に帰着させて考えることにした。 $N$ が 3 の倍数でなかったとしても、 $N = pq$ としたとき、

まず最初の $3q$ 個を 3 個ずつの $q$ グループに分ける。
残りの $(p-3)q$ 個を $q$ グループに振り分けていく

という風にできる。よって、 $N = 3n$ の場合ができれば OK。これは色々手を動かしていると、できた (下のコード参照)！

コード

#include <bits/stdc++.h>
using namespace std;

bool is_prime(long long n) {
    if (n <= 1) return false;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p == 0) return false;
    }
    return true;
}

void print(vector<vector<int>> res) {
    cout << res.size() << endl;
    for (auto v : res) {
        sort(v.begin(), v.end());
        cout << v.size();
        for (auto p : v) cout << " " << p;
        cout << endl;
    }
}

vector<vector<int>> sub(int W) {
    vector<vector<int>> res;
    int sum = W * 9;
    for (int i = 0; i < W; ++i) {
        int a = i*2 + 1;
        int j = (i + W/2) % W;
        int b = W*2+1 + j*2;
        int c = sum - a - b;
        res.push_back(vector<int>({a, b, c}));
    }
    return res;
}

int num(int h, int w, int W) {
    int id = h * W + w;
    return id * 2 + 1;
}

bool check(vector<vector<int>> res) {
    set<long long> se;
    for (auto v : res) {
        long long sum = 0;
        for (auto p : v) sum += p;
        se.insert(sum);
    }
    return se.size() == 1;
}

void solve(int N) {
    if (is_prime(N)) {
        cout << "impossible" << endl;
        return;
    }

    long long H = 3, W = 1;
    for (; H * H <= N; ++H) {
        if (N % H == 0) {
            W = N / H;
            break;
        }
    }
    vector<vector<int>> res;
    if (N % 2 == 0) {
        for (int i = 1, j = N*2-1; i <= j; i += 2, j -= 2) {
            res.push_back(vector<int>({i, j}));
        }
        print(res);
        return;
    }

    res = sub(W);
    int width = (H - 3) / 2;
    for (int i = 0; i < W; ++i) {
        for (int j = 0; j < width; ++j) {
            int h = j + 3;
            int w = i;
            res[i].push_back(num(h, w, W));
        }
        for (int j = 0; j < width; ++j) {
            int h = j + width + 3;
            int w = W - i - 1;
            res[i].push_back(num(h, w, W));
        }
    }
    print(res);
}

int main() {
    int N;
    while (cin >> N) solve(N);
}