唯一神特图创造了一种新的游戏:新 24 点,并在迪司博德大陆上的人类种国家艾尔奇亚王国上流行。
定义了一种很新的 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 所能表示的范围。