Question

Pentru multimea de numere {x1, x2, x3, x4, ..., xN} (N>=3) multimea sumelor de perechi este
{x1+x2, x1+x3, x1+x4, x2+x3,x2+x4,x3+x4, ...,}. (s_k = x_i + x_j, i != j). Se da multimea sumelor
de perechi si se cere gasirea multimii initiale. Multimea sumelor de perechi se da intr-o ordine
oarecare.
Intrare
6 105 11 101 110 15
Ieșire
1 5 10 100

Answer 1

Răspuns:

#include <iostream>

#include <fstream>

#include <algorithm>

using namespace std;

ifstream f("sumeperechi.in");

ofstream g("sumeperechi.out");

int n, a[1000], v[500], sum;

int main()

{

   while (f >> sum)

   {

       a[++n]=sum;

   }

   sort(a+1, a+n+1);

   

   int i=3, k=2, p=1;

   while (i<=n)

   {

       ++k;

       v[k]=(a[i]+a[i-1]-a[p])/2;

       p=i; i=i+k;

   }

   v[1]=a[2]-v[3]; v[2]=a[1]-v[1];

   for (i=1; i<=k; ++i)

       g << v[i] << " ";

}

Explicație:

explicaţia e cam dificilă... am mers pe cărări întortochiate până am ajuns la asta. Din start am înţeles că trebuie de sortat crescător sumele date, pe care le-am plasat într-un vector a[] . După, mi-a venit ideea să le plasez, din vectorul sortat, într-o matrice indexată de la 1 la m, deasupra diagonalei principale. Primul element în x[1][2], parcă r fi x1+x2, după completez coloanele de sus în jos şi de la stânga la dreapta până la diagonala principală şi indicii matricei ne sugerează ce sume se pun în ea. în x[1][3] suma x1+x3 şamd. Aici apărea problema care este cardinalul multimii căutate, adică m. Se poate calcula matematic ca Combinări din m câte 2 este egal cu n, numărul de sume introduse. Se obţine m*(m-1)=2*n şi cu un ciclu se poate găsi m. Dacă vei plasa într+o matrice sumele 6 7 9 10 12 13 13  

 14 16 19 care sunt sumele pentru vectorul (căutat) 2 4 5 8 11, atunci cred că vei înţelege logica următoarei secvenţe care determină vectorul căutat.

for (j=2; j<=m; ++j)

{ for (i=1; i<j; ++i) x[i][j]=a[p++]; }, astfel am plasat sumele in matrice

Acum urmeaza gasirea vectorului cautat dupsumele plasate in matrice

for (i=2; i<m; ++i)

{for (j=3; j<=m; ++j) v[j]=(x[i][j+x[i-1][j]-x[i-1][j-1])/2; }

v[1]=x[1][3]-v[3]; v[2]=x[1][2]-v[1];

Dupa m-am dezis de matrice, ca sa nu mai aflu m, si am realizat varianta postata la care matricea mi-a sugerat ideea