← 返回题目列表

Codeforces · 2078/D

D. 诈骗游戏广告

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

考虑以下游戏。

在这个游戏中,一个关卡由 $$$n$$$ 对门组成。每对包含一个左门和一个右门。每个门执行以下两个操作之一:

  • 加法运算 (+ 一个):将车道中的人数增加恒定量$$$a$$$。
  • 乘法运算 (x 一个):将车道中的当前人数乘以整数 $$$a$$$。这意味着该车道上的人数增加了 $$$(a - 1)$$$ 乘以当前人数。

每次行动获得的额外人员可以分配到任一车道。然而,人们已经在巷子里 不能 被移动到另一条车道。

最初,每条车道上有一个人。您的任务是确定关卡结束时可以达到的最大总人数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \le 30$$$) — 门对的数量。

每个测试用例的接下来 $$$n$$$ 行提供每个门对中左门和右门的信息。每个门的信息以以下形式给出 + $$$a$$$ ($$$1 \le a \le 1000$$$) 或 x $$$a$$$ ($$$2 \le a \le 3$$$) 对于某个整数 $$$a$$$。

输出

对于每个测试用例,输出一个整数 - 关卡结束时的最大总人数。

示例

输入
复制

4
3
+ 4 x 2
x 3 x 3
+ 7 + 4
4
+ 9 x 2
x 2 x 3
+ 9 + 10
x 2 + 1
4
x 2 + 1
+ 9 + 10
x 2 x 3
+ 9 x 2
5
x 3 x 3
x 2 x 2
+ 21 + 2
x 2 x 3
+ 41 x 3

输出
复制

32
98
144
351

注意

在第一种情况下,这是一种最佳地玩这个游戏的可能方法。

最初,我们在左车道上有 $$$l=1$$$ 人,在右车道上有 $$$r=1$$$ 人。

通过第一对门后,我们从左门获得 $$$4$$$ 人,从右门获得 $$$1 \cdot (2-1) = 1$$$ 人,总共 $$$4+1=5$$$ 人。我们将 $$$2$$$ 人分配到左车道,将 $$$3$$$ 人分配到右车道。这导致左车道上有 $$$l=1+2=3$$$ 人,右车道上有 $$$r=1+3=4$$$ 人。

通过第二对大门后,我们从左门获得 $$$3 \cdot (3-1) = 6$$$ 人,从右门获得 $$$4 \cdot (3-1) = 8$$$ 人,总共 $$$6+8=14$$$ 人。我们将 $$$7$$$ 人分配到左车道,将 $$$7$$$ 人分配到右车道。这导致左车道上有 $$$l=3+7=10$$$ 人,右车道上有 $$$r=4+7=11$$$ 人。

穿过最后一对门后,我们从左门获得$$$7$$$人,从右门获得$$$4$$$人,总共$$$7+4=11$$$人。我们将 $$$6$$$ 人分配到左车道,将 $$$5$$$ 人分配到右车道。这导致左车道上有 $$$l=10+6=16$$$ 人,右车道上有 $$$r=11+5=16$$$ 人。

最后总人数为$$$16+16=32$$$。