B - Black or White 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

2 以上の整数 N,M と整数 K が与えられます。あなたは縦 N マス、横 M マスのマス目のうち K マスを黒色で、残りの NM - K マスを白色で塗る必要があります。

ここで、色を塗ったマス目に対して損失を以下のように定義します。

  • 2 \times 2 の正方形をなす 4 マスの部分で、黒色と白色で塗られているマスがともに 2 個であるものの個数

損失が最小となるマス目の塗り方を 1 つ示してください。

T 個のテストケースが与えられるので、それぞれについて答えてください。

制約

  • 入力は全て整数
  • 1 \leq T \leq 10^5
  • 2 \leq N, M \leq 1500
  • 0 \leq K \leq NM
  • 1 つの入力に含まれるテストケースについて、NM の総和は 4 \times 10^6 以下

入力

入力は以下の形式で標準入力から与えられる。ここで、\mathrm{case}_i は i 番目のテストケースを意味する。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる。

N M K

出力

各テストケースに対する答えを順に改行区切りで出力せよ。

各テストケースでは N 行にわたり、0 と 1 からなる M 文字の文字列を出力せよ。

ここで、i 行目に出力した文字列の j 文字目が 0 の場合、上から i 番目、左から j 番目のマスを白色で塗ったことを、1 の場合は黒色で塗ったことを表す。

損失が最小となるマス目の塗り方が複数ある場合、そのうちの 1 つを出力せよ。損失の最小値は出力しないことに注意せよ。

入力例 1

2
2 2 2
2 3 0

出力例 1

10
01
000
000
  • 1 番目のテストケースについて、損失は 1 であり、これが最小値です。
  • 2 番目のテストケースについて、損失は 0 であり、これが最小値です。