D - NMパズル Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 600 点

問題文

あなたはNMパズルと呼ばれるパズルゲームで遊んでいる。 このゲームは、1 から NM までの整数のうち一つが書かれたカード NM 枚と、N 行 M 列の盤面を用いて行われる。ここで、カードに書かれた整数に重複は無い。

このゲームの目的は、スコアが K となるようにカードを配置することである。 盤面上の全てのマスにちょうど1枚ずつカードを配置した時、(各行の転倒数の和) + (各列の転倒数の和)がスコアとなる。

スコアがちょうど K となるようなカードの配置を一つ出力しなさい。

なお、条件を満たす出力が複数ある場合、どれを出力しても良い。

ここで、転倒数は以下のように定義される。

C_{ij} は盤面の i 行 j 列目のマスに配置するカードに書かれた整数を表す。ただし、左上を 1 行 1 列目、右下を N 行 M 列目とする。

  • 行 i (1 ≦ i ≦ N) の転倒数とは、 1 ≦ j < j’ ≦ M かつ C_{ij} > C_{ij’} を満たす組 (j, j’) の個数である。
  • 列 j (1 ≦ j ≦ M) の転倒数とは、 1 ≦ i < i’ ≦ N かつ C_{ij} > C_{i’j} を満たす組 (i, i’) の個数である。

制約

  • 入力は全て整数である。
  • 1 ≦ N, M ≦ 100
  • 0 ≦ K ≦ NM(M-1)/2 + MN(N-1)/2
  • スコアが K となるようなカードの配置は必ず存在する。

入力

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

N M K

出力

条件を満たすカードの配置を以下の形式に従って標準出力に出力せよ。

  • C_{ij} は盤面の i 行 j 列目のマスに配置するカードに書かれた整数を表す。
  • 整数と整数は1つの半角スペースで区切られている。
  • C_{ij} は互いに異なり、1 から NM までの整数でなければならない。
  • C_{ij} は以下のように N 行 M 列で出力する。
C_{11} C_{12} … C_{1M}
C_{21} C_{22} … C_{2M}
:
C_{N1} C_{N2} … C_{NM}

入力例 1

2 3 5

出力例 1

6 1 4
2 5 3

このように配置すると、転倒数は1行目が2, 2行目が1, 1列目が1, 2列目が0, 3列目が1となるため、スコアは5となり条件を満たす。

なおこれは出力例であり、他にも条件を満たす出力は存在する。