問題一覧 > 通常問題

No.1398 調和の魔法陣 (構築)

レベル : / 実行時間制限 : 1ケース 3.153秒 / メモリ制限 : 315 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 84
作問者 : CuriousFairy315CuriousFairy315 / テスター : 37zigen37zigen
7 ProblemId : 4589 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-02-18 13:48:12

問題文

315さんは魔法陣の勉強をしています。
魔法陣には五芒星や六芒星、円陣など様々な形のものがあり、そこに適切な強さの触媒を置くことで効果を発揮します。
今回書く魔法陣は長方形を縦に $H$ 個、横に $W$ 個 に分割し、その各マスに触媒を置くことで効果を発揮するものです。
しかし、魔法陣は調和を保っていないと魔力の伝播にムラが発生し、最終的に術式が破綻してしまいます。
今回書く魔法陣が調和を保っている状態とは、どのマスについてもそのマスを中心とする $3 \times 3$ マスの範囲の触媒の強さの合計 $S$ が等しいことを言います。
すなわち、 $M_{y, x}$ をマス $(x, y)$ の触媒の強さとすると、 $1 \leq x \leq W, 1 \leq y \leq H$ を満たす整数 $x, y$ 全てに対し $\sum_{i=y-1}^{y+1} \sum_{j=x-1}^{x+1} M_{i, j} = S$ である必要があります。
またこの時、魔法陣の強さは $S$ となります。
315さんは強さが $1$ 以上 $9$ 以下の触媒をたくさん持っているので、この触媒を適切に配置することで強さ $X$ の調和を保っている魔法陣を作りたいです。
触媒は1マスに高々1個まで配置できる(配置しないこともできる)ので、 $1 \leq x \leq W, 1 \leq y \leq H$ を満たす整数 $x, y$ 全てに対し $0 \leq M_{y, x} \leq 9$ であり、それ以外の $x, y$ に対し $M_{y, x} = 0$ となります。
魔法陣に触媒を置く方法は全部で $10^{WH}$ 通りもありますが、その中で調和を保っている魔法陣の置き方はどのようなものがあるでしょうか?
$W, H, X$ が与えられるので、強さ $X$ の調和を保っている魔法陣を一つ構築してください。

入力

$W\ H\ X$

  • $1 \leq W, H \leq 600$
  • $0 \leq X \leq 81$
  • 入力は全て整数である

出力

もし大きさが縦に $H$ 、横に $W$ で強さが $X$ の調和を保っている魔法陣が作れるならばその魔法陣を、そうでないならば-1を出力してください。
魔法陣の出力は $M_{y,x}$ をマス $(x, y)$ の触媒の強さとして、以下のようになります。

$M_{1, 1}M_{1, 2} \cdots M_{1, W}$
$\vdots$
$M_{H, 1}M_{H,2} \cdots M_{H, W}$
最後に改行してください。

サンプル

サンプル1
入力
2 2 6
出力
12
30

条件を満たす魔法陣であれば、上と同じ魔法陣である必要はありません。
例えば

60
00
も正答となります。

サンプル2
入力
5 2 4
出力
11011
11011

サンプル3
入力
3 3 81
出力
-1

315さんの持っている触媒はそこまで強くないので、このような強力な魔法陣を書くことはできません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。