2023 软件学院 ACM 集训队筛选赛

Problem E. 新24点

唯一神特图创造了一种新的游戏:新 24 点,并在迪司博德大陆上的人类种国家艾尔奇亚王国上流行。

/uploads/20230610/16863746906470.png

定义了一种很新的 24 点游戏的规则为:给定一个目标数 b,构造出长为 n 的取值在一到九的个位操作数 a_i(1\le i\le n,1\le a_i\le 9),并为这些操作数间添加四则运算操作符(加、减、乘、地板除)和不超过一个括号,使其经由运算能得到 b

形式化地说,设 1\le op\le 4 代表四则运算符序号,四则运算为 a\ op\ b a\ op\ b=\begin{cases} x+y,&op=1\\ x-y,&op=2\\ x\times y,&op=3\\ \lfloor\dfrac xy\rfloor,&op=4 \end{cases} 请注意四则运算满足从左到右、先乘除后加减的优先级。例如 a=(1,3,2),op=(1,3),则 a_1\ op_1\ a_2\ op_2\ a_3=1+3\times 2=7

若不添加括号,你需要构造长为 n-1 的运算符序列 op_i(1\le i\le n-1),满足: a_1\ op_1\ a_2\ op_2\ a_3\cdots a_{n-1}\ op_{n-1}\ a_n=b 若添加括号,你需要构造长为 n-1 的运算符序列 op_i(1\le i\le n-1) 和括号起止位置 1\le l < r\le n,满足: a_1\ op_1\ a_2\cdots a_{l-1}\ op_{l-1}\ (a_l\ op_l\ a_{l+1}\cdots a_{r-1}\ op_{r-1}\ a_r) \ op_r\ a_{r+1}\cdots a_{n-1}\ op_{n-1}\ a_n=b 其中括号内的优先级最高,优先计算括号内的结果并去括号,然后再按照上述规则运算。

给定整数 b,请你找出一种新 24 点的解决方案,构造出长为 n(\mathbf{1\le n\le 40}) 的操作数序列 a,及其对应运算符序列 op 和括号位置,使得该新 24 点有解。

特别地,如果对于给定的 b 无解,请输出无解。

输入

输入一行一个整数 b(0\le b\le 10^9)

输出

若有解,输出输出一行一个字符串,代表你构造的操作序列。字符串应仅含 123456789()+-*/ 这几种字符,不能有任何空格。且输出的字符串应符合题意,即:①数字的两边如有字符不能是数字;② +/*- 字符的两边只能是数字或括号;③左括号在右括号前,且括号内子串符合 ①② 要求。

如果有多个方案,输出任意一个即可。

若无解,输出一行一个字符串 oops

样例

标准输入 复制文本
6
标准输出 复制文本
6
标准输入 复制文本
580
标准输出 复制文本
4+9*8*8
标准输入 复制文本
69994
标准输出 复制文本
(2*2*2*2*5*5*5*5-1)*7+1

提示

你应当保证你所构造出的表达式在运算过程的所有中间结果不超过 C++ long long 所能表示的范围。

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 50
通过 5

A B C D E F G H

赛后有滚榜,有兴趣可留下来观看。
H题时限开大,题目重判中
F题补充限制条件:每个非叶子节点必须拥有两个子节点。
G题中的才艺天赋值必须为整数