2308. 哈利的魔法炼金炉
1000ms
256MB
简单
枚举算法
题目描述
在霍格沃茨的魔药课上，哈利拿到了一尊神奇的“顺序炼金炉”和 4 个排好顺序的魔药材料，它们的魔力值分别是 4 个小于 10 的正整数。
哈利不能改变这些材料的投放顺序，但他必须在每两个相邻材料之间施加一种融合咒语。可选的咒语有四种：
- `+`（融合）
- `-`（提炼）
- `*`（增幅）
- `/`（稀释，采用整除法，即舍弃余数，向零取整，例如 $-3 / 2 = -1$，$5 / 2 = 2$）
这个炼金炉非常死板，工作时**严格从左往右**进行计算，完全无视数学上的乘除优先律（即先算前两个材料的融合，其结果再与第三个材料融合，其结果再与第四个材料融合）。
斯内普教授要求哈利炼制出的终极魔药魔力值刚好等于指定的目标魔力值 $n$。请帮哈利计算一下，一共有多少种不同的咒语组合方式，能够炼制出魔力值刚好为 $n$ 的魔药？
输入格式
- 第一行包含 4 个小于 10 的正整数，表示 4 个材料的初始魔力值，每个数之间用一个空格隔开。
- 第二行包含一个整数 $n$，表示教授要求的目标魔力值。
输出格式
- 输出一行一个整数，表示能够得到目标魔力值 $n$ 的不同咒语添加方案数。
样例 1
输入 (Input)
1 2 3 4 24
输出 (Output)
2
- 输入的 4 个正整数 $a_i$ 满足 $1 \le a_i \le 9$。
- 目标值 $n$ 为整数。
- **样例说明**：
对于材料魔力值为 `1 2 3 4`，目标值为 `24`，共有 2 种咒语组合：
- `((1 + 2) + 3) * 4 = 24`（咒语依次为 `+`、`+`、`*`）
- `((1 * 2) * 3) * 4 = 24`（咒语依次为 `*`、`*`、`*`）
- **算法提示**：
由于只有 4 个数字，中间只有 3 个位置可以施加咒语。每个位置有 4 种选择，总共只有 $4^3 = 64$ 种咒语组合。
可以直接通过三重循环（或深度优先搜索 DFS）枚举所有可能的咒语组合，模拟从左往右的计算过程，最后统计结果等于 $n$ 的组合个数。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功