天下一プログラマーコンテスト2013予選B

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


Time limit時間制限 : 3sec / Memory limitメモリ制限 : 64MB


問題文

高橋君のいたずらによりバラバラにされた天下一プログラマーコンテストのポスターを見て触発されたショウヘイ君は、天下一プログラマーコンテストのポスターを下図のように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つの「特殊なピース」を持つ、条件を満たした分割方法の一例である。


Source name

天下一プログラマーコンテスト2013 予選B

Submit提出する