아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Matrix Inversion

시간 제한1초메모리 제한1024 MB

요약
1부터 N^2까지를 N×N 격자에 채워 행 우선 순열의 역전 개수가 X, 열 우선 순열의 역전 개수가 Y가 되게 만든다.
난이도

보통10점 중 7점

유형
구현, 조합론, 그리디, 수학
정답자
아직 제출이 없습니다

문제

You have an NN by NN grid board, which is initially empty. You will write an integer to each cell, using each integer from 11 to N2N^2 exactly once. Let M_i,jM\_{i,j} be the integer written on the cell in the ii-th row from the top and the jj-th column from the left.

Let's define sequences AA and BB as follows:

  • A=M_1,1,M_1,2,…,M_1,N,M_2,1,M_2,2,…,M_2,N,…,M_N,NA = M\_{1,1}, M\_{1,2}, \dots, M\_{1,N}, M\_{2,1}, M\_{2,2}, \dots, M\_{2,N}, \dots, M\_{N,N}
  • B=M_1,1,M_2,1,…,M_N,1,M_1,2,M_2,2,…,M_N,2,…,M_N,NB = M\_{1,1}, M\_{2,1}, \dots, M\_{N,1}, M\_{1,2}, M\_{2,2}, \dots, M\_{N,2}, \dots, M\_{N,N}

For example, when the board looks like this,

1 3 4
2 7 6
9 8 5

AA and BB are defined as follows.

  • A=1,3,4,2,7,6,9,8,5A = 1,3,4,2,7,6,9,8,5
  • B=1,2,9,3,7,8,4,6,5B = 1,2,9,3,7,8,4,6,5

You are given integers N,X,YN, X, Y. Find a way to fill in the cells so that the inversion numbers of AA and BB are XX and YY respectively, or report that it is impossible to do so.

Note: an inversion number of a sequence C=c_1,c_2,…,c_N×NC = c\_1, c\_2, \dots, c\_{N \times N} is the number of pairs (i,j)(i, j) s.t. both i<ji < j and c_i>c_jc\_i > c\_j are satisfied.

입력

Input is given from Standard Input in the following format:

NN XX YY

출력

If there is no solution, print 'No'.

Otherwise, print the answer in the following format:

Yes

M_1,1M\_{1,1} M_1,2M\_{1,2} …\dots M_1,NM\_{1,N}

M_2,1M\_{2,1} M_2,2M\_{2,2} …\dots M_2,NM\_{2,N}

⋮\vdots

M_N,1M\_{N,1} M_N,2M\_{N,2} …\dots M_N,NM\_{N,N}

If there are multiple solutions, you can print any of them.

제한

  • 2≤N≤3002 \leq N \leq 300
  • 0≤X,Y≤N2(N2−1)20 \leq X, Y \leq \frac{N^2(N^2 - 1)}{2}

예제1

  1. 예제 1

    입력
    3 8 13
    
    예상 출력
    Yes
    1 3 4
    2 7 6
    9 8 5