C - 天下一ジグソーパズルふたたび

Contest Duration: 2013-08-23(Fri) 09:00 - 2013-08-23(Fri) 11:00 (local time) (120 minutes) Back to Home

C - 天下一ジグソーパズルふたたび Editorial

Time Limit: 3 sec / Memory Limit: 64 MB

高橋君のいたずらによりバラバラにされた天下一プログラマーコンテストのポスターを見て触発されたショウヘイ君は、天下一プログラマーコンテストのポスターを下図のように $N \times M$ のピースに分割したパズルを作ることにした。

上下左右に隣り合うピースの一辺は一方が凸に他方が凹になっており、外周の辺は直線になっている。このとき、一辺が直線で、残り三辺が凹になっているピースを「特殊なピース」とし、これを可能な限り多くなるように配置した時の「特殊なピース」の個数を答えよ。

ただし、四辺が凹のピースは $A$ 個以上、四辺が凸のピースは $B$ 個以下にするという条件が与えられる。

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

 $N$   $M$   $A$   $B$

パズルの縦幅 $N$ 、横幅 $M$ ( $2 \leq N, M \leq 8$ ) 、四辺が凹のピースの数の下限 $A$ ( $A \geq 0$ ) 、四辺が凸のピースの数の上限 $B$ ( $B \geq 0$ ) が、スペースで区切られて、それぞれ整数で与えられる。
$A + B \leq (N-2) \times (M-2)$
少なくとも $1$ 通りは条件を満たす分割方法が存在する。

「特殊なピース」の数の最大値を標準出力に $1$ 行で出力せよ。
なお、行の終端には改行が必要である。

3 3 0 1

下図は4つの「特殊なピース」を持つ、条件を満たした分割方法である。

3 4 1 1

下図は3つの「特殊なピース」を持つ、条件を満たした分割方法の一例である。