No.1087 転倒数の転倒数
タグ : / 解いたユーザー数 14
作問者 :
tyawanmusi
/ テスター :
QCFium
問題文
長さ$M$の整数列$X$において、$f(X)$を次のように定義します。
- $X_i > X_j$である$(i,j)$の個数$(1 \le i < j \le M)$
整数$N$が与えられます。
$N$行$N$列の行列$S$を考えます。上から$i$行目、左から$j$列目の要素を$S_{i,j}$とします。
ここで、$0 \le S_{i,j} \le 10^6$とします。
整数列$A$を次のように定義します。
- $A_i = f([S_{i,1},S_{i,2}, \dots ,S_{i,N}])(1 \le i \le N)$
- $B_j = f([S_{1,j},S_{2,j}, \dots ,S_{N,j}])(1 \le j \le N)$
$f(A)+f(B)=K$である$S$を構築してください。構築不可能である時はそのことを報告してください。
答えが複数ある場合はその一例を求めてください。
制約
- $1 \le N \le 1000$
- $0 \le K \le 10^9$
- $N,K$は整数
入力
$N\ K$
入力は$1$行で与えられます。
$N,K$が空白区切りで入力されます。
出力
構築不可能である場合はNoを1行に出力してください。
そうではない場合、Yesを1行に出力したあとに$N$行出力してください。
$i+1$行目には$S_{i,1},S_{i,2}, \dots ,S_{i,N}$を空白区切りで出力してください。
サンプル
サンプル1
入力
3 3
出力
Yes
3 2 3
2 3 1
1 3 2
$A_1 = f([3,2,3]) = 1$
$A_2 = f([2,3,1]) = 2$
$A_3 = f([1,3,2]) = 1$
$B_1 = f([3,2,1]) = 3$
$B_2 = f([2,3,3]) = 0$
$B_3 = f([3,1,2]) = 2$
よって、$A=[1,2,1]$,$B=[3,0,2]$となります。
$f(A)+f(B)=f([1,2,1])+f([3,0,2])=1+2=3$となり、この$S$は条件を満たします。
サンプル2
入力
5 0
出力
Yes
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
きれ～
サンプル3
入力
4 0
出力
Yes
7 6 5 4
6 5 4 3
5 4 3 2
4 3 2 1
はい。
サンプル4
入力
4 12
出力
Yes
4 3 2 1
3 4 1 2
2 1 4 3
1 2 3 4
この形、個人的に好きです。
サンプル5
入力
5 13
出力
Yes
9 8 3 8 2
4 6 8 3 9
7 5 4 1 5
6 2 6 2 4
6 1 6 5 9
これはヒントですが、このサンプルはほぼ意味ありません。
サンプル6
入力
1 1000000000
出力
No
このサンプルは意味ありますか？私はないと思います。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。