← 返回题目列表

Codeforces · 1986/D

D. 数学问题

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

给定一个字符串 $$$s$$$,长度为 $$$n > 1$$$,由从 $$$0$$$ 到 $$$9$$$ 的数字组成。您必须在该字符串中准确插入 $$$n - 2$$$ 符号 $$$+$$$(加法)或 $$$\times$$$(乘法)以形成有效的算术表达式。

在这个问题中,符号不能放在字符串$$$s$$$的第一个字符之前或最后一个字符之后,并且两个符号不能连续写入。另请注意,字符串中数字的顺序无法更改。让我们考虑 $$$s = 987009$$$:

- 从该字符串中,可以获得以下算术表达式: $$$9 \times 8 + 70 \times 0 + 9 = 81$$$, $$$98 \times 7 \times 0 + 0 \times 9 = 0$$$, $$$9 + 8 + 7 + 0 + 09 = 9 + 8 + 7 + 0 + 9 = 33$$$。请注意,数字 $$$09$$$ 被视为有效,并简单地转换为 $$$9$$$。
- 从该字符串中,无法获得以下算术表达式:$$$+9 \times 8 \times 70 + 09$$$(符号只能放在数字之间),$$$98 \times 70 + 0 + 9$$$(因为有 $$$6$$$ 数字,所以必须恰好有 $$$4$$$ 符号)。

算术表达式的结果是根据数学规则计算的 - 首先执行所有乘法运算,然后执行加法。您需要找到通过将 $$$n - 2$$$ 加法或乘法符号精确插入到给定字符串 $$$s$$$ 中可以获得的最小结果。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。然后是他们的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 20$$$) — 字符串 $$$s$$$ 的长度。

每个测试用例的第二行包含一个长度为$$$n$$$的字符串$$$s$$$,由从$$$0$$$到$$$9$$$的数字组成。

输出

对于每个测试用例,输出算术表达式的最小结果,该算术表达式可以通过在给定字符串中插入 $$$n - 2$$$ 加法或乘法符号来获得。

示例

输入 #1

18
2
10
2
74
2
00
2
01
3
901
3
101
5
23311
6
987009
7
1111111
20
99999999999999999999
20
00000000000000000000
4
0212
18
057235283621345395
4
1112
20
19811678487321784121
4
1121
4
2221
3
011

输出 #1

10
74
0
1
9
1
19
0
11
261
0
0
0
12
93
12
24
0

注意

在前四个测试用例中,我们无法添加符号,因此答案将是原始数字。

在第五个测试用例中,最佳答案如下:$$$9 \times 01 = 9 \times 1 = 9$$$。

在第六个测试用例中,最佳答案如下:$$$1 \times 01 = 1 \times 1 = 1$$$。

在第七个测试用例中,最佳答案如下:$$$2 + 3 + 3 + 11 = 19$$$。

在第八个测试用例中,最佳答案之一如下所示:$$$98 \times 7 \times 0 + 0 \times 9 = 0$$$。