CF1461F Mathematical Expression

Barbara 上数学课迟到了，作为惩罚，老师让她在一张纸上解一道题。Barbara 看着纸上的内容，只看到 $n$ 个数字 $a_1, a_2, \ldots, a_n$，没有任何数学符号。老师向 Barbara 解释，她需要在这些数字之间插入可以使用的符号，使得最终表达式的值尽可能大。为了让 Barbara 知道可以使用哪些符号，老师给了她一个字符串 $s$，其中包含了所有可用的符号。 很容易发现，Barbara 需要在数字之间总共插入 $n-1$ 个符号。表达式必须以数字开头，并且所有插入的符号都必须是允许的（即包含在 $s$ 中）。注意，乘法的优先级高于加法和减法，加法和减法优先级相同，且从左到右依次计算。请帮助 Barbara 构造一个使表达式结果最大的方案！

输入的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示纸上的数字个数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 9$），其中 $a_i$ 表示第 $i$ 个数字。 第三行包含一个字符串 $s$（$1 \le |s| \le 3$），表示表达式中允许使用的符号。保证字符串只包含符号 “-”、"+" 和 "\*"，且所有符号互不相同。

输出 $n$ 个数字，中间用 $n-1$ 个符号隔开，构成一个结果最大的数学表达式。如果有多个答案，输出任意一个均可。

对于第一个样例，以下答案也都是合法的："2+2+0"、"2+2-0"、"2\*2+0"。 由 ChatGPT 4.1 翻译