PTIT136C spoj - Tìm dãy số

Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT136C/

1. Đề bài PTIT136C spoj

Cho trước một dãy số dương có N phần tử. Bạn biết trước tổng của bất kì 2 phần tử nào trong dãy số, hãy tìm dãy số ban đầu.

Input

Dòng đầu tiên là N, số phần tử của dãy số. (2 <= N <= 1000)

N dòng sau, mỗi dòng gồm N số (mỗi số <= 100 000) mô tả ma trận biểu diễn tổng của 2 phần tử trong dãy.

* S(i,j) = 0 nếu i = j.

* S(i,j) = A[i] + A[j] với i ≠ j, là tổng của phần tử thứ i và thứ j trong dãy số.

Output

In ra trên 1 dòng dãy số cần tìm. Input luôn đảm bảo có 1 đáp số duy nhất.

Example

Input1:

2
0 2
2 0

Ouput1:

1 1

Input2:

4
0 3 6 7
3 0 5 6
6 5 0 9
7 6 9 0

Ouput2:

2 1 4 5

2. Gợi ý PTIT136C spoj

– Bài này nếu bạn để ý bạn sẽ dễ dàng nhận thấy, chỉ cần cộng trừ những ô trên bảng cho trước thì sẽ thu được kết quả cho trước :))…=))

2 code tham khảo dưới đây không dùng chung 1 công thức nhưng có ý tưởng giống nhau là dùng công thức để tính… các bạn có thể tham khảo:

3. Code tham khảo PTIT136C spoj

a. Code pascal

const   fi='';
        nmax=1000;

type
        data=longint;
var
        f:text;
        A:array[1..nmax,1..nmax] of data;
        B:array[1..nmax] of data;
        N:data;


procedure docfile;
var     i,j:data;
begin
        assign(f,fi); reset(f);
        readln(f,n);
        for i:=1 to n do
                for j:=1 to n do
                        read(f,a[i,j]);
        close(f);
end;

procedure xuli;
var     i,j:data;
begin
        B[1]:=(A[1,2]+a[1,3]-a[2,3]) div 2;
        B[2]:=(a[1,2]-a[1,3]+a[2,3]) div 2;
        write(b[1],' ',b[2],' ');
        for i:=3 to n do
                write((A[1,2]-A[1,i]-a[2,i]) div (-2),' ');
end;

begin
        docfile;
        xuli;
end.

b. Code c++

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int a[n+1][n+1],s[n+1][n+1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin >> a[i][j];
    if(n==2) cout << a[1][2]/2 << " " << a[1][2]/2;
    else
    {
        for(int j=2;j<n;j++)
        {
            s[j][j+1]=a[1][j]-a[1][j+1];
            if(j==2) cout << a[1][2]-(s[j][j+1]+a[j][j+1])/2 << " ";
            cout << (s[j][j+1]+a[j][j+1])/2 << " ";
            if(j==n-1) cout << a[j][j+1]- (s[j][j+1]+a[j][j+1])/2;
        }
    }
}

PTIT136C spoj – Tìm dãy số