
 53通过
 227提交
 题目提供者 洛谷
 评测方式 云端评测
 标签 贪心 POI 2012 高性能
 难度 省选/NOI
 时空限制 1000ms / 128MB
最新讨论 显示
题目描述
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.
设有n个互不相同的正整数{X1,X2,…Xn}，任取两个Xi,Xj(i≠j)，能算出Xi+Xj。现在所有取法共n*(n1)/2个和，要你求出X1,X2,…Xn。
3<=n<=300, 每个正整数不超过10^8
输入输出格式
输入格式：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., .
输入输出样例
说明
设有n个互不相同的正整数{X1,X2,…Xn}，任取两个Xi,Xj(i≠j)，能算出Xi+Xj。现在所有取法共n*(n1)/2个和，要你求出X1,X2,…Xn。
3<=n<=300, 每个正整数不超过10^8