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 通りは条件を満たす分割方法が存在する。
部分点
- A = 0, B = (N-2) \times (M-2) の入力に正解すると、120 点満点に対して部分点として、30 点が与えられる。
- M, N \leq 4 の入力に正解すると、120 点満点に対して部分点として 40 点が与えられる。
出力
「特殊なピース」の数の最大値を標準出力に 1 行で出力せよ。
なお、行の終端には改行が必要である。
入力例 1
3 3 0 1
出力例 1
4
下図は4つの「特殊なピース」を持つ、条件を満たした分割方法である。
入力例 2
3 4 1 1
出力例 2
3
下図は3つの「特殊なピース」を持つ、条件を満たした分割方法の一例である。