P13180 [GCJ 2017 Finals] Operation

在 Code Jam，我们非常喜欢玩一个叫做 **Operation** 的游戏。（不，这和外科手术没有任何关系；你为什么会这么想呢？）这个游戏是用卡牌来进行的，每张卡牌上都标有一个基本的算术运算（加法、减法、乘法或除法）$\mathbf{O}_i$，以及该运算的右操作数 $\mathbf{V}_i$，它是一个整数。例如，一张卡牌可能写着 $+\ 0$，或者 $-\ -2$，又或者 $/\ -4$ —— 注意，操作数可以是负数，也可以是零，但带有除法操作的卡牌，其操作数绝不会是 $0$。 每一轮游戏会选定一个初始整数值 $\mathbf{S}$，并摆出一组 $\mathbf{C}$ 张卡牌。玩家需要自行决定这些卡牌的出牌顺序，每张卡牌都必须且只能使用一次。之后，这些操作会按照卡牌顺序依次作用在起始值 $\mathbf{S}$ 上，最终得到一个结果。 虽然卡牌上的操作数都是整数，但实际运算是在有理数范围内执行的。例如，假设初始值为 $5$，卡牌分别为 $+\ 1$、$-\ 2$、$*\ 3$ 和 $/\ -2$。如果按照上述顺序出牌，最终结果是 $(5 + 1 - 2) * 3 / (-2) = -6$。注意，所有操作都严格按照卡牌顺序依次执行，不考虑运算符优先级。另一方面，如果你选择的顺序是 $-\ 2$、$/\ -2$、$+\ 1$、$*\ 3$，那么结果就是 $((5 - 2) / (-2) + 1) * 3 = -3 / 2$。这个例子中，这样的顺序实际上可以获得这一组卡牌能得到的最大值。 给定一组卡牌，你能算出通过合理排序后，最终可能得到的最大结果吗？请将答案以最简分数形式输出，分母需为正数。

输入的第一行给出测试用例的数量 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试用例。每组测试用例的第一行为两个整数 $\mathbf{S}$ 和 $\mathbf{C}$，分别表示游戏的起始值和卡牌数量。接下来的 $\mathbf{C}$ 行，每行描述一张卡牌，包括一个字符 $\mathbf{O}_i$（表示操作类型，可能为 $+$、$-$、$*$ 或 $/$）和一个整数 $\mathbf{V}_i$（表示操作数）。

对于每组测试用例，输出一行，内容为 `Case #x: y z`，其中 $x$ 表示测试用例编号（从 1 开始），$y$ 和 $z$ 是整数，满足 $y/z$ 是该组卡牌能获得的最大最终值，且 $y$ 和 $z$ 互质（除了 $1$ 和 $-1$ 以外没有公约数），并且 $z$ 必须严格大于 $0$。

**样例解释** 在样例第 1 组中，最优策略是先打出 $*\ 2$ 卡牌，再打 $-\ 3$ 卡牌，最终结果为 $-1$。按题目要求，最简分数表达为 $-1\ 1$。 样例第 2 组对应题面第三段的例子。 样例第 3 组，无论卡牌顺序如何，答案都相同。注意，答案的分子大到无法用 64 位整数表示。 样例第 4 组，最大结果为 $1$。一种可行顺序为：$/\ -1$、$*\ 0$、$-\ -1$。 样例第 5 组，唯一合法的答案为 $0\ 1$。$0\ 2$ 不合法，因为可以约分；$0\ -1$ 也不合法，因为分母必须为正数。 **限制条件** - $1 \leq T \leq 100$。 - $-1000 \leq S \leq 1000$。 - 对所有 $i$，$O_i$ 为 $+$、$-$、$*$ 或 $/$。 - 对所有 $i$，$-1000 \leq V_i \leq 1000$。 - 若 $O_i = /$，则 $V_i \neq 0$。 **小数据集（10 分，测试集 1 - 可见）** - 时间限制：~~60~~ 15 秒。 - $1 \leq C \leq 15$。 **大数据集（20 分，测试集 2 - 隐藏）** - 时间限制：~~120~~ 30 秒。 - $1 \leq C \leq 1000$。 翻译由 GPT4.1 完成。