406867: GYM102586 G Matrix Inversion

Memory Limit:1024 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Matrix Inversiontime limit per test1.0 smemory limit per test1024 megabytesinputstandard inputoutputstandard output

You have an $$$N$$$ by $$$N$$$ grid board, which is initially empty. You will write an integer to each cell, using each integer from $$$1$$$ to $$$N^2$$$ exactly once. Let $$$M_{i,j}$$$ be the integer written on the cell in the $$$i$$$-th row from the top and the $$$j$$$-th column from the left.

Let's define sequences $$$A$$$ and $$$B$$$ as follows:

  • $$$A = 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}, \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

$$$A$$$ and $$$B$$$ are defined as follows.

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

You are given integers $$$N, X, Y$$$. Find a way to fill in the cells so that the inversion numbers of $$$A$$$ and $$$B$$$ are $$$X$$$ and $$$Y$$$ respectively, or report that it is impossible to do so.

Note: an inversion number of a sequence $$$C = c_1, c_2, \dots, c_{N \times N}$$$ is the number of pairs $$$(i, j)$$$ s.t. both $$$i < j$$$ and $$$c_i > c_j$$$ are satisfied.

Input

Input is given from Standard Input in the following format:

$$$N$$$ $$$X$$$ $$$Y$$$

Constraints:

  • $$$2 \leq N \leq 300$$$
  • $$$0 \leq X, Y \leq \frac{N^2(N^2 - 1)}{2}$$$
Output

If there is no solution, print 'No'.

Otherwise, print the answer in the following format:

Yes

$$$M_{1,1}$$$ $$$M_{1,2}$$$ $$$\dots$$$ $$$M_{1,N}$$$

$$$M_{2,1}$$$ $$$M_{2,2}$$$ $$$\dots$$$ $$$M_{2,N}$$$

$$$\vdots$$$

$$$M_{N,1}$$$ $$$M_{N,2}$$$ $$$\dots$$$ $$$M_{N,N}$$$

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

ExampleInput
3 8 13
Output
Yes
1 3 4 
2 7 6 
9 8 5 

加入题单

上一题 下一题 算法标签: