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となり条件を満たす。
なおこれは出力例であり、他にも条件を満たす出力は存在する。