Tìm dãy số (Spoj)

Link bài: http://www.spoj.com/PTIT/problems/PTIT136C/

14080. Tìm dãy số

Mã bài: PTIT136C

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

 

Giải thuật Tìm dãy số:

Để ý qua các bạn sẽ thấy a[1][2]-a[1][3]+a[2][3]=2*a[2] =>> a[2] … Lần lượt với các số còn lại (Tự kiểm chứng nha ) 😀

Code:

 

Share
Share