B - Magic Square Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

3 以上の奇数 N が与えられます。

N 行 N 列のマス目があり、はじめどのマスも空白です。 今から、以下の手順に従ってこのマス目の各マスに整数を書き込みます。 なお、上から i+1 行目、左から j+1 列目 (0\leq i<N, 0\leq j<N) のマスを (i,j) と表記することとします。

  1. マス (0,\frac{N-1}{2}) に 1 を書き込む。
  2. 次の操作を N^2-1 回繰り返す。
    • 前回整数を書き込んだマスを (r,c)、書き込んだ整数を k としたとき、マス ((r-1) \bmod N, (c+1) \bmod N) が空白ならばそのマスに、そうでなければマス ((r+1) \bmod N,c) に k+1 を書き込む。 ここで、x \bmod N は x を N で割ったあまりを表す。

この手順においてそれぞれのマスに書き込まれる整数を求めてください。 なお、どのマスもちょうど 1 回だけ整数を書き込まれることが証明できます。

制約

  • 3\leq N \leq 99
  • N は奇数

入力

入力は以下の形式で標準入力から与えられる。

N

出力

マス (i,j) に書き込まれる整数を a_{i,j} として、以下の形式で出力せよ。

a_{0,0} a_{0,1} \dots a_{0,N-1}
\vdots
a_{N-1,0} a_{N-1,1} \dots a_{N-1,N-1}

入力例 1

3

出力例 1

8 1 6
3 5 7
4 9 2

以下のように各マスに整数が書き込まれていきます。

  1. マス (0,\frac{3-1}{2})=(0,1) に 1 を書き込む。
  2. マス ((0-1) \bmod 3, (1+1) \bmod 3)=(2,2) は空白なので、そこに 2 を書き込む。
  3. マス ((2-1) \bmod 3, (2+1) \bmod 3)=(1,0) は空白なので、そこに 3 を書き込む。
  4. マス ((1-1) \bmod 3, (0+1) \bmod 3)=(0,1) は空白ではないので、マス ((1+1) \bmod 3,0)=(2,0) に 4 を書き込む。
  5. \vdots

入力例 2

5

出力例 2

17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9

Score : 200 points

Problem Statement

You are given an odd number N that is at least 3.

There is a grid with N rows and N columns, where all cells are initially empty. Now, you will write integers in each cell of this grid according to the following procedure. Let (i,j) denote the cell at the (i+1)-th row from the top and (j+1)-th column from the left (0\leq i<N, 0\leq j<N).

  1. Write 1 in cell (0,\frac{N-1}{2}).
  2. Repeat the following operation N^2-1 times:
    • Let (r,c) be the cell where an integer was written last time, and k be the integer written. If cell ((r-1) \bmod N, (c+1) \bmod N) is empty, write k+1 in that cell; otherwise, write k+1 in cell ((r+1) \bmod N,c). Here, x \bmod N denotes the remainder when x is divided by N.

Find the integer that will be written in each cell in this procedure. It can be proved that each cell will have an integer written in it exactly once.

Constraints

  • 3\leq N \leq 99
  • N is an odd number.

Input

The input is given from Standard Input in the following format:

N

Output

Let a_{i,j} be the integer written in cell (i,j), and print it in the following format:

a_{0,0} a_{0,1} \dots a_{0,N-1}
\vdots
a_{N-1,0} a_{N-1,1} \dots a_{N-1,N-1}

Sample Input 1

3

Sample Output 1

8 1 6
3 5 7
4 9 2

Integers are written in each cell as follows:

  1. Write 1 in cell (0,\frac{3-1}{2})=(0,1).
  2. Cell ((0-1) \bmod 3, (1+1) \bmod 3)=(2,2) is empty, so write 2 there.
  3. Cell ((2-1) \bmod 3, (2+1) \bmod 3)=(1,0) is empty, so write 3 there.
  4. Cell ((1-1) \bmod 3, (0+1) \bmod 3)=(0,1) is not empty, so write 4 in cell ((1+1) \bmod 3,0)=(2,0).
  5. \vdots

Sample Input 2

5

Sample Output 2

17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9