No.1087 Inversion Number of Inversion Numbers
タグ : / 解いたユーザー数 15
作問者 :
QCFium
Problem Statement
For an integer sequence $X$ of length $M$, define $f(X)$ as follows.
- The number of pairs $(i,j)$ such that $X_i > X_j$ $(1 \le i < j \le M)$
You are given an integer $N$.
Consider a matrix $S$ with $N$ rows and $N$ columns. Let $S_{i,j}$ denote the element in the $i$-th row from the top and the $j$-th column from the left.
Here, $0 \le S_{i,j} \le 10^6$.
Define the integer sequence $A$ as follows.
- $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)$
Construct $S$ such that $f(A)+f(B)=K$. If this is impossible, report so.
If there are multiple answers, find any one of them.
Constraints
- $1 \le N \le 1000$
- $0 \le K \le 10^9$
- $N,K$ are integers
Input
$N\ K$
The input is given in $1$ line.
$N,K$ are given separated by a space.
Output
If the construction is impossible, print No on 1 line.
Otherwise, print Yes on 1 line, and then print $N$ lines.
On line $i+1$, print $S_{i,1},S_{i,2}, \dots ,S_{i,N}$ separated by spaces.
Sample
Sample 1
Input
3 3
Output
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$
Thus, $A=[1,2,1]$, $B=[3,0,2]$.
We get $f(A)+f(B)=f([1,2,1])+f([3,0,2])=1+2=3$, so this $S$ satisfies the condition.
Sample 2
Input
5 0
Output
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
So pretty~
Sample 3
Input
4 0
Output
Yes
7 6 5 4
6 5 4 3
5 4 3 2
4 3 2 1
Yep.
Sample 4
Input
4 12
Output
Yes
4 3 2 1
3 4 1 2
2 1 4 3
1 2 3 4
Personally, I like this shape.
Sample 5
Input
5 13
Output
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
As a hint: this sample is almost meaningless.
Sample 6
Input
1 1000000000
Output
No
Does this sample have any point? I don't think it does.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。