COCI '12 Contest 6 #2 Sume

Points: 7

Time limit: 1.0s

Memory limit: 32M

Problem type

Once upon a time, there existed a sequence $A$ ~A~ consisting of $N$ ~N~ positive integers. You don't know the sequence itself, but you do know the sum of every two elements of the sequence. Find the sequence $A$ ~A~!

Input Specification

The first line of input contains the positive integer $N$ ~N~ $(2 \le N \le 1000)$ ~(2 \le N \le 1000)~.

Each of the following $N$ ~N~ lines contains $N$ ~N~ positive integers smaller than or equal to $100\,000$ ~100\,000~, forming the table $S$ ~S~. The following relations hold: $S(i, j) = A[i] + A[j]$ ~S(i, j) = A[i] + A[j]~ for $i \neq j$ ~i \neq j~, and $S(i, j) = 0$ ~S(i, j) = 0~ for $i = j$ ~i = j~. Here $S(i, j)$ ~S(i, j)~ denotes the number in the $i^\text{th}$ ~i^\text{th}~ row and $j^\text{th}$ ~j^\text{th}~ column of the table, and $A[i]$ ~A[i]~ denotes the $i^\text{th}$ ~i^\text{th}~ element of the sequence $A$ ~A~.