← 返回题目列表

AtCoder · abc403_f

I. 最短一公式

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

分数: 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+2
  • 1-1
  • 1/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)