题目描述

A famous Byteotian physicist Byteasar is studying a new constituent of matter - squarks.

These are quite exotic particles that never exist alone but always in pairs.

Moreover, squarks of a particular kind form pairs only with squarks of different kinds.

After years of studies Byteasar has established that there are different kinds of squarks.

Squarks of each kind have a unique mass, which is a positive integer multiple of (an appropriate) unit.

Byteasar has also measured the total mass of each of the possible pairs of squarks.

According to standard Byteotian model of physics, the mass of a pair of squarks equals the sum of the masses of the two squarks forming it.

Now Byteasar desires to determine the individual masses of squarks of every kind.

He has asked your help in writing a program that will determine all solutions to this puzzle, i.e., will reconstruct all configurations of squark masses that are consistent with his previous measurements.

输入格式

In the first line of the standard input there is a single integer () that denotes the number of different kinds of squarks.

In the second line there are positive integers, separated by single spaces, that denote the total masses of all possible pairs of squarks.

The mass of every pair does not exceed .

For each two different kinds of squarks, the mass of the pair they form is given on the input exactly once.

  The masses on the input are given in a random order.

In tests worth 32% of the points the following conditions hold in addition:

and the mass of every pair of squarks does not exceed .

输出格式

In the first line of the standard output your program should print the number of possible solutions to the problem.

In the lines that follow it should report successive solutions, one per line.

Each solution should consist of different positive integers, namely the masses of squarks of all kinds.

In every solution these should be given in increasing order and separated by single spaces.

Solutions can be reported in arbitrary order, but they cannot be repeated.

You may assume that for each test data there exists at least one solution, i.e., .

题目大意

题目描述

译自 POI 2012 Stage 3. Day 0「Squarks」

给定 $n$ 个不同的正整数两两的和，求这 $n$ 个正整数的所有可能。

输入格式

第一行一个正整数 $n (1 \le n \le 300)$，表示正整数的数量。

接下来一行有 $\frac{n(n-1)}2$ 个正整数，表示两两正整数的和，不超过 $10^8$，顺序随机。

输出格式

第一行输出一个正整数 $k$，表示解的个数。

接下来 $k$ 行每行按递增顺序输出 $n$ 个正整数，表示一组可能的解。

可以以任意顺序输出解。保证存在一组解。

数据范围

对于 $32\%$ 的数据保证 $n \le 20$ 且任何两个正整数的和不超过 $2000$.

对于所有数据保证 $n \le 300$ 且任何两个正整数的和不超过 $10^8$.

翻译与 checker 来自于 LibreOJ。

4
3 5 4 7 6 5

1
1 2 3 4