// Author: Balakrishnan V
// Given a set of pairwise sums, this function computes the inverse -
// (the set of numbers that correspond to these pairwise sums).
// If multiple solutions exists, one of them is output.
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <math.h>
#include <vector>
using namespace std;
#define MAXN 7
int N;
double sum_A;
vector<double> S;
// The indices for a(0)+a(1), a(0)+a(2), ..., a(0)+a(N-2)
int chosen_indices[MAXN-1];
vector<double> solution;
bool dfs(int id, int to_choose) {
if(to_choose==0) {
double sum_indices = 0;
for(int j=0;j<N-1;j++) {
sum_indices += S[chosen_indices[j]];
}
vector<double> A(N, 0);
A[0] = (sum_indices - sum_A) / (N-2);
for(int j=1;j<N;j++) {
A[j]=S[chosen_indices[j-1]]-A[0];
}
vector<double> all_sums;
for(int i=0;i<N;i++)
for(int j=i+1;j<N;j++)
all_sums.push_back(A[i]+A[j]);
sort(all_sums.begin(), all_sums.end());
bool ok = true;
for(int i=0;i<(N*(N-1))/2;i++) {
if(fabs(all_sums[i]-S[i]) > 1e-9) {
ok=false;
}
}
if(ok) {
solution = A;
return true;
} else {
return false;
}
}
if(id>=(N*(N-1))/2)
return false;
chosen_indices[to_choose-1]=id;
if(dfs(id+1, to_choose-1))
return true;
return dfs(id+1, to_choose);
}
int main() {
printf("Enter the number of numbers.\n");
cin>>N;
if(N<=2 || N>MAXN) {
printf("N should be between 3 and %d\n",MAXN);
return 0;
}
printf("Enter all the %d pairwise sums.\n", (N*(N-1))/2);
sum_A=0;
S.resize((N*(N-1))/2);
for(int i=0;i<S.size();i++) {
cin>>S[i];
sum_A+=S[i];
}
sort(S.begin(), S.end());
sum_A /= N-1;
if(dfs(0,N-1)) {
printf("Solution found.\n");
sort(solution.begin(), solution.end());
for(int i=0;i<N;i++)
printf("%lf ",solution[i]);
printf("\n");
} else {
printf("No solution found.\n");
}
}
Ly8gQXV0aG9yOiBCYWxha3Jpc2huYW4gVgovLyBHaXZlbiBhIHNldCBvZiBwYWlyd2lzZSBzdW1zLCB0aGlzIGZ1bmN0aW9uIGNvbXB1dGVzIHRoZSBpbnZlcnNlIC0KLy8gKHRoZSBzZXQgb2YgbnVtYmVycyB0aGF0IGNvcnJlc3BvbmQgdG8gdGhlc2UgcGFpcndpc2Ugc3VtcykuCi8vIElmIG11bHRpcGxlIHNvbHV0aW9ucyBleGlzdHMsIG9uZSBvZiB0aGVtIGlzIG91dHB1dC4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGNzdHJpbmc+CiNpbmNsdWRlIDxtYXRoLmg+CiNpbmNsdWRlIDx2ZWN0b3I+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgTUFYTiA3CgppbnQgTjsKZG91YmxlIHN1bV9BOwp2ZWN0b3I8ZG91YmxlPiBTOwoKLy8gVGhlIGluZGljZXMgZm9yIGEoMCkrYSgxKSwgYSgwKSthKDIpLCAuLi4sIGEoMCkrYShOLTIpCmludCBjaG9zZW5faW5kaWNlc1tNQVhOLTFdOwoKdmVjdG9yPGRvdWJsZT4gc29sdXRpb247Cgpib29sIGRmcyhpbnQgaWQsIGludCB0b19jaG9vc2UpIHsKICAgIGlmKHRvX2Nob29zZT09MCkgewogICAgICAgIGRvdWJsZSBzdW1faW5kaWNlcyA9IDA7CiAgICAgICAgZm9yKGludCBqPTA7ajxOLTE7aisrKSB7CiAgICAgICAgICAgIHN1bV9pbmRpY2VzICs9IFNbY2hvc2VuX2luZGljZXNbal1dOwogICAgICAgIH0KICAgICAgICB2ZWN0b3I8ZG91YmxlPiBBKE4sIDApOwogICAgICAgIEFbMF0gPSAoc3VtX2luZGljZXMgLSBzdW1fQSkgLyAoTi0yKTsKICAgICAgICBmb3IoaW50IGo9MTtqPE47aisrKSB7CiAgICAgICAgICAgIEFbal09U1tjaG9zZW5faW5kaWNlc1tqLTFdXS1BWzBdOwogICAgICAgIH0KICAgICAgICB2ZWN0b3I8ZG91YmxlPiBhbGxfc3VtczsKICAgICAgICBmb3IoaW50IGk9MDtpPE47aSsrKQogICAgICAgICAgICBmb3IoaW50IGo9aSsxO2o8TjtqKyspCiAgICAgICAgICAgICAgICBhbGxfc3Vtcy5wdXNoX2JhY2soQVtpXStBW2pdKTsKICAgICAgICBzb3J0KGFsbF9zdW1zLmJlZ2luKCksIGFsbF9zdW1zLmVuZCgpKTsKICAgICAgICBib29sIG9rID0gdHJ1ZTsKICAgICAgICBmb3IoaW50IGk9MDtpPChOKihOLTEpKS8yO2krKykgewogICAgICAgICAgICBpZihmYWJzKGFsbF9zdW1zW2ldLVNbaV0pID4gMWUtOSkgewogICAgICAgICAgICAgICAgb2s9ZmFsc2U7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgaWYob2spIHsKICAgICAgICAgICAgc29sdXRpb24gPSBBOwogICAgICAgICAgICByZXR1cm4gdHJ1ZTsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICByZXR1cm4gZmFsc2U7CiAgICAgICAgfQogICAgfQoKICAgIGlmKGlkPj0oTiooTi0xKSkvMikKICAgICAgICByZXR1cm4gZmFsc2U7CiAgICAKICAgIGNob3Nlbl9pbmRpY2VzW3RvX2Nob29zZS0xXT1pZDsKICAgIGlmKGRmcyhpZCsxLCB0b19jaG9vc2UtMSkpCiAgICAgICAgcmV0dXJuIHRydWU7CiAgICByZXR1cm4gZGZzKGlkKzEsIHRvX2Nob29zZSk7Cn0KCmludCBtYWluKCkgewogICAgcHJpbnRmKCJFbnRlciB0aGUgbnVtYmVyIG9mIG51bWJlcnMuXG4iKTsKICAgIGNpbj4+TjsKICAgIGlmKE48PTIgfHwgTj5NQVhOKSB7CiAgICAgICAgcHJpbnRmKCJOIHNob3VsZCBiZSBiZXR3ZWVuIDMgYW5kICVkXG4iLE1BWE4pOwogICAgICAgIHJldHVybiAwOwogICAgfQogICAgcHJpbnRmKCJFbnRlciBhbGwgdGhlICVkIHBhaXJ3aXNlIHN1bXMuXG4iLCAoTiooTi0xKSkvMik7CiAgICAKICAgIHN1bV9BPTA7CiAgICBTLnJlc2l6ZSgoTiooTi0xKSkvMik7CiAgICBmb3IoaW50IGk9MDtpPFMuc2l6ZSgpO2krKykgewogICAgICAgIGNpbj4+U1tpXTsKICAgICAgICBzdW1fQSs9U1tpXTsKICAgIH0KICAgIHNvcnQoUy5iZWdpbigpLCBTLmVuZCgpKTsKICAgIHN1bV9BIC89IE4tMTsKICAgIGlmKGRmcygwLE4tMSkpIHsKICAgICAgICBwcmludGYoIlNvbHV0aW9uIGZvdW5kLlxuIik7CiAgICAgICAgc29ydChzb2x1dGlvbi5iZWdpbigpLCBzb2x1dGlvbi5lbmQoKSk7CiAgICAgICAgZm9yKGludCBpPTA7aTxOO2krKykKICAgICAgICAgICAgcHJpbnRmKCIlbGYgIixzb2x1dGlvbltpXSk7CiAgICAgICAgcHJpbnRmKCJcbiIpOwogICAgfSBlbHNlIHsKICAgICAgICBwcmludGYoIk5vIHNvbHV0aW9uIGZvdW5kLlxuIik7CiAgICB9Cn0=