分数: 500 点
问题陈述
给你一个正整数 N.
在所有由字符组成的有效算术表达式中 1, +, *, (,和 ),找到最小长度之一,其值为 N.
更正式地说,在字符串中 S 满足以下所有条件,找到最小长度之一:
- S 符合符号
<expr>在 BNF 如下。 - 表示的表达式的值 S is N.
<expr> ::= <term> | <expr> "+" <term>
<term> ::= <factor> | <term> "*" <factor>
<factor> ::= <number> | "(" <expr> ")"
<number> ::= "1" | "1" <number>
符合以下条件的字符串 <expr> 包括:
1111+111代表 1111+111.(1+1)*(1+1)代表 (1+1)\times(1+1).(11+(1+1)*(1+1))+1代表 (11+(1+1)\times(1+1))+1.
不符合的字符串 <expr> 包括:
(1+1)(1+1)1+21-11/1)1(1++1+1(+1)1*+1
约束
- 1 \le N \le 2000
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
输出
打印解决方案。
示例输入 1
9
示例输出 1
(1+1+1)*(1+1+1)
值为 9 包括:
(1+1+1)*(1+1+1)1+1+1+1+1+1+1+1+1(1+1)*(1+1)*(1+1)+1
其中最短的是 (1+1+1)*(1+1+1).
示例输入 2
11
示例输出 2
11
示例输入 3
403
示例输出 3
1+(1+1+1)*(1+11+11+111)