問題一覧 > 通常問題

No.1974 2x2 Flipper

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 73
作問者 : magstamagsta / テスター : tassei903tassei903
4 ProblemId : 7934 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-06-07 20:05:11

問題文

縦 $H$ 行、横 $W$ 列の白黒に塗られたマス目があります。最初は全部白で塗られています。$i$ 行目 $j$ 列目のマスを $(i,j)$ と表記します。

以下の操作を有限回行ったときの、黒で塗られているマス目の数の最大値と、それを満たす具体的なマス目の状態を求めてください。

操作

$1 \leq i \leq H-1, 1 \leq j \leq W-1$ を満たす $i,j$ をとる。

$(i,j),\ (i+1,j),\ (i,j+1),\ (i+1,j+1)$ それぞれにおいて、白で塗られている場合は黒に、黒で塗られている場合は白に塗り替える。

制約

  • $\displaystyle 1 \leq H,W \leq 1000$
  • 入力はすべて整数である

入力

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

$H\ \ W$

出力

答えを以下の形式で出力し、最後に改行せよ。

複数通りの答えが考えられる場合は、そのどれを出力してもよい。

$ans$ は黒で塗られているマス目の数の最大値を意味している。

$A_{i,j}$ は求めたマス目の $i$ 行目 $j$ 列目の要素を表しており、$0$ のとき白、$1$ のとき黒である。

$ans$
$A_{1,1}\ \ A_{1,2} \ \dots \ A_{1,W}$
$A_{2,1}\ \ A_{2,2} \ \dots \ A_{2,W}$
$:$
$A_{H,1}\ \ A_{H,2} \ \dots \ A_{H,W}$

サンプル

サンプル1
入力
2 3
出力
4
1 1 0
1 1 0

$1$ 回の操作で $i=1,j=1$ をとることによりマス目の状態は上の出力のようになります。

有限回の操作で黒で塗られているマス目の数が $5$ 以上にすることができないことが示せるため、最大値は $4$ となります。

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