J - Zero Diag Matrix
Flavor
2
s
1024
MB
600
点
問題文
長さ $N$ の整数列 $A$ が与えられる。以下の条件を満たす $N\times N$ の 2 次元配列 $M$ が存在するか判定し、存在するなら 1 つ出力せよ。
- $M_{ij}\ge0$
- $0\le M_{ii}\le10^{-5}$
- $|A_i-\sum_jM_{ij}|\le10^{-5}$
- $|A_i-\sum_jM_{ji}|\le10^{-5}$
- $i\neq j$ かつ $i\neq k$ のとき $sgn(A_j-A_k)(M_{ij}-M_{ik})\ge-10^{-5}$
- $i\neq j$ かつ $i\neq k$ のとき $sgn(A_j-A_k)(M_{ji}-M_{ki})\ge-10^{-5}$
ただし $sgn(x)=\begin{cases}-1&(x<0)\\0&(x=0)\\1&(x>0)\end{cases}$ とする。
制約
- $1\le N\le10^3$
- $0\le A_i<10^9$
- 入力はすべて整数
入力
入力は以下の形式で与えられます。
$N$
$A_1\ A_2\ A_3\ \cdots\ A_N$
出力
2次元配列 $M$ が存在しないときは No と出力してください。
No
Yes
$M_{11}\ M_{12}\ M_{13}\ \cdots\ M_{1N}$
$M_{21}\ M_{22}\ M_{23}\ \cdots\ M_{2N}$
$M_{31}\ M_{32}\ M_{33}\ \cdots\ M_{3N}$
$\ \vdots$
$M_{N1}\ M_{N2}\ M_{N3}\ \cdots\ M_{NN}$
数を出力するときは小数点に . (ピリオド) を使用し、0123456789. の 11 種以外の文字や 2 つ以上のピリオドを含まないようにしてください。
入力例 1
4
4 2 3 1
出力例 1
Yes
0 1 2 1
1 0 1 0
2 1 0 0
1 0 0 0
入力例 2
3
1 1 1
出力例 2
Yes
0.0 0.5 0.5
0.5 0.0 0.5
0.5 0.5 0.0