#include<stdio.h> #include<memory.h> #include<algorithm> #include<list> #define M 100 #define N 12 using namespace std; list <int> sum; int ans[N], n, flag = 0, checkans[M], temp[M], cnt = 0; int checker(){ memset(checkans, 0, sizeof(int) * M); cnt = 0; for(int i = 1; i<=n; i++){ for(int j = i+1; j<=n; j++){ checkans[cnt++] = ans[i] + ans[j]; } } sort(checkans, checkans+cnt); for(int i = 0; i<cnt; i++){ if(checkans[i] != temp[i])return 0; } return 1; } void back(int s, list <int>::iterator iter){ list <int>::iterator it1, it2, temp, tempit; int tempsum; if(s == n+1 && checker()){ flag = 1; return; } for(it1 = iter; it1 != sum.end() && !flag; it1++){ temp = it1; temp++; for(it2 = temp; it2 != sum.end() && !flag; it2++){ tempsum = (ans[s-1] + ans[s-2] + *it1 + *it2)/2; ans[s] = tempsum - ans[s-1] - ans[s-2]; if(ans[s-2] <= ans[s-1] && ans[s-1] <= ans[s]){ tempit = find(it2, sum.end(), ans[s-1] + ans[s]); //back(s+1, find(it2, sum.end(), ans[s-1] + ans[s])); back(s+1, tempit); } } } } int main(void) { int m, i, tempsum, start = 1; while(scanf("%d", &n) == 1){ if(start == 1){ start = 0; } else if(start == 0){ printf("\n"); } flag = 0; memset(temp, 0, sizeof(int) * M); memset(ans, 0, sizeof(int) * N); while(!sum.empty())sum.pop_back(); for(i = 0; i<n*(n-1)/2; i++){ scanf("%d", &temp[i]); } m = i; sort(temp, temp + m); for(i = 2; i<m; i++){ sum.push_back(temp[i]); } list<int>::iterator iter, tempit; for(iter = sum.begin(); iter!=sum.end(); iter++){ tempsum = (temp[0] + temp[1] + *iter)/2; ans[1] = tempsum - *iter; ans[2] = tempsum - temp[1]; ans[3] = tempsum - temp[0]; if(ans[1] <= ans[2] && ans[2] <= ans[3]){ tempit = find(sum.begin(), sum.end(), ans[2]+ans[3]); //back(4, find(sum.begin(), sum.end(), ans[2] + ans[3])); back(4, tempit); if(flag)break; } } if(!flag)printf("Impossible"); else{ for(i = 1; i<=n; i++){ printf("%d", ans[i]); if(i != n)printf(" "); } } } return 0; }
10546028 10202 Pairsumonious Numbers Accepted C++ 0.008 2012-08-31 07:07:56