← 返回题目列表

AtCoder · tenka1_2013_qualB_c

C. 天下一拼图又来了

中文机器翻译题面 查看原题

問題文

受到高桥君恶作剧把天下第一程序员大赛的海报弄得支离破碎的启发,翔平君决定将天下第一程序员大赛的海报按照下图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 个“特殊拼块”的、符合条件的划分方法的一个例子。