難易度評価

難易度を1〜10段階で評価できます。投票はあとから変更・取り消しできます。

難易度(投票) 未投票 (0票)

投票の分布

まだ投票はありません。

  1. Lv.10票
  2. Lv.20票
  3. Lv.30票
  4. Lv.40票
  5. Lv.50票
  6. Lv.60票
  7. Lv.70票
  8. Lv.80票
  9. Lv.90票
  10. Lv.100票

難易度の目安を見る ↗

ログインして難易度を投票

外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

Subgrid Sum

作成者 npnp

難易度(作成者設定) Lv.5

難易度(投票) 未投票 (0票)

解法のヒントになることがあります。
実行時間制限
2 秒
メモリ制限
512 MiB

この問題は沼津高専 高専祭でnpnpが出題した景品付き問題を一般化した問題です(一般化前はN=8,M=4N=8,M=4)。

問題文

整数 N,MN, M が与えられます。ただし、MM は偶数です。

NN 行 NN 列のグリッド AA を考えます。上から ii 行目、左から jj 列目のマスに書かれた整数を Ai,jA_{i,j} とします。

以下の条件を満たすグリッド AA を 11 つ構築してください。

  • 11 から N2N^2 までの整数がちょうど 11 回ずつ現れる。すなわち、{Ai,j∣1≤i,j≤N}={1,2,…,N2}\{A_{i,j} \mid 1 \le i, j \le N\} = \{1, 2, \ldots, N^2\} である。
  • 1≤x≤N−M+11 \le x \le N - M + 1, 1≤y≤N−M+11 \le y \le N - M + 1 を満たす任意の整数 x,yx, y に対して、左上のマスが (x,y)(x, y) である M×MM \times M 部分グリッドに含まれる M2M^2 個の整数の和はすべて等しい。すなわち、

∑i=xx+M−1∑j=yy+M−1Ai,j\sum_{i=x}^{x+M-1} \sum_{j=y}^{y+M-1} A_{i,j}

は x,yx, y の選び方によらず一定である。

条件を満たすグリッドが複数存在する場合、どれを出力しても正解と判定されます。

制約

  • 2≤M≤N≤10002 \le M \le N \le 1000
  • MM は偶数である
  • 入力はすべて整数である

入力形式

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

N M

出力形式

NN 行出力してください。ii 行目には Ai,1,Ai,2,…,Ai,NA_{i,1}, A_{i,2}, \ldots, A_{i,N} を空白区切りで出力してください。

入力例 1

5 2

出力例 1

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

スペシャルジャッジ問題:提出の出力を検証コードで判定します。