Luogu | P1286 两数之和 | 数学


Description

我们知道从 $n$ 个非负整数中任取两个相加共有 $\frac{n(n-1)}{2}$ 个和,现在已知这 $\frac{n(n-1)}{2}$ 个和值,要求 $n$ 个非负整数。


Input Format

输入文件有若干行。

每行一组数据,包含 $\frac{n(n-1)}{2}$ 个空格隔开的非负整数,其中第一个数表示 $n$ ,其余 $\frac{n(n-1)}{2 }$ 个数表示和值,每个数不超过 $100000$ 。文件末以 EOF 结尾。


Output Format

输出文件若干行,对应每一个输入,该行按从小到大的次序依次输出一组满足要求的 $n$ 个非负整数,相邻两个整数之间用一个空格隔开;若问题无解则输出 Impossible


Input Sample

Sample 01

3 1269 1160 1663


Output Sample

Sample 01

383 777 886


Data Range

$2 < n \le 10$。


Solution

将给定的输入从小到大排序,设为 $S$,并设可能的答案序列为 $A$(从小到大)。可以发现 $S_1 = A_1 + A_2, S_2 = A_1 + A_3$。所以通过枚举 $A_1$ 即可直接得到 $A_2$ 和 $A_3$。接下来标记 $S_1, S_2$ 和 $A_2 + A_3$ ,然后寻找最小的未标记的 $S$ 即为 $A_1 + A_4$ 。将其标记,得到 $A_4$ 然后与当前已知其它元素一起组合,并标记,再继续找最小的为 $A_1 + A_5$ …循环至无法标记或出解为止。


Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

using std::sort;

inline void Read(int &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

int N;
int cnt;

int res[105];
int mrk[105];
int src[105];

bool Mark(int x){
    rep(i,1,cnt)
        if(mrk[i]&&src[i]==x)
            return --mrk[i],true;
    return false;
}

bool Valid(int x){
    wipe(res,0);
    rep(i,1,cnt)
        mrk[i]=1;
    mrk[1]=0;
    mrk[2]=0;
    res[1]=x;
    res[2]=src[1]-res[1];
    res[3]=src[2]-res[1];
    if(!Mark(res[2]+res[3]))
        return false;
    rep(i,4,N){
        rep(j,1,cnt){
            if(mrk[j]){
                mrk[j]--;
                res[i]=src[j]-res[1];
                break;
            }
        }
        rep(j,2,i-1)
            if(!Mark(res[j]+res[i]))
                return false;
    }
    rep(i,1,N)
        printf("%d ",res[i]);
    printf("\n");
    return true;
}

int main(){
    while(~scanf("%d",&N)){
        cnt=(N-1)*N/2;
        bool done=false;
        rep(i,1,cnt)
            scanf("%d",&src[i]);
        sort(src+1,src+1+(N-1)*N/2);
        rep(i,1,src[1]/2){
            if(Valid(i)){
                done=true;
                break;
            }
        }
        if(!done)
            printf("Impossible\n");
    }
    return 0;
}