実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
N 行 N 列の非負整数を成分とする行列 C が与えられます。すべての (i,j) について C_{i,j}=A_i+B_j を満たすような非負整数列 A_1,A_2,\ldots,A_N と B_1,B_2,\ldots,B_N の組が存在するか判定し、存在するなら一つ出力してください。
制約
- 1 \leq N \leq 500
- 0 \leq C_{i,j} \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N C_{1,1} C_{1,2} \ldots C_{1,N} C_{2,1} C_{2,2} \ldots C_{2,N} : C_{N,1} C_{N,2} \ldots C_{N,N}
出力
- 条件を満たすA,B の組が存在しない場合
一行目にNo
と出力せよ。
No
- 条件を満たすA,B の組が存在する場合
一行目に Yes
と出力せよ。
二行目には各要素を空白で区切って数列 A を出力せよ。
三行目には各要素を空白で区切って数列 B を出力せよ。
条件を満たす解が複数存在する場合は、どれを出力してもよい。
Yes A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
入力例 1
3 4 3 5 2 1 3 3 2 4
出力例 1
Yes 2 0 1 2 1 3
A,B は非負整数列であることに注意してください。
入力例 2
3 4 3 5 2 2 3 3 2 4
出力例 2
No
Score : 400 points
Problem Statement
Given is an N \times N matrix C whose elements are non-negative integers. Determine whether there is a pair of sequences of non-negative integers A_1,A_2,\ldots,A_N and B_1,B_2,\ldots,B_N such that C_{i,j}=A_i+B_j for every (i, j). If the answer is yes, print one such pair.
Constraints
- 1 \leq N \leq 500
- 0 \leq C_{i,j} \leq 10^9
Input
Input is given from Standard Input in the following format:
N C_{1,1} C_{1,2} \ldots C_{1,N} C_{2,1} C_{2,2} \ldots C_{2,N} : C_{N,1} C_{N,2} \ldots C_{N,N}
Output
- If no pair A, B satisfies the condition:
Print No
in the first line.
No
- If some pair A, B satisfies the condition:
In the first line, print Yes
.
In the second line, print the elements of A, with spaces in between.
In the third line, print the elements of B, with spaces in between.
If multiple pairs satisfy the condition, any of them will be accepted.
Yes A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
Sample Input 1
3 4 3 5 2 1 3 3 2 4
Sample Output 1
Yes 2 0 1 2 1 3
Note that A and B consist of non-negative integers.
Sample Input 2
3 4 3 5 2 2 3 3 2 4
Sample Output 2
No