F - Shortest One Formula Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

正整数 N が与えられます。

1, +, *, (, ) のみからなる数式のうち、値が N となるものの中で、文字列としての長さが最小のものを一つ求めてください。

より厳密には、以下の条件をすべて満たす文字列 S のうち長さが最小のものを一つ求めてください。

  • S は下の BNF 記法 の <expr> シンボルに従う文字列である。
  • S が表す数式の値は 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\leq N\leq 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

値が 9 となるような数式のうち、長さが最小となるものは (1+1+1)*(1+1+1) です。

入力例 2

11

出力例 2

11

入力例 3

403

出力例 3

1+(1+1+1)*(1+11+11+111)

Score : 500 points

Problem Statement

You are given a positive integer N.

Among all valid arithmetic expressions consisting of the characters 1, +, *, (, and ), find one of the minimum length whose value is N.

More formally, among the strings S satisfying all of the following conditions, find one of the minimum length:

  • S conforms to the symbol <expr> in the BNF below.
  • The value of the expression represented by S is N.
<expr>   ::= <term> | <expr> "+" <term>
<term>   ::= <factor> | <term> "*" <factor>
<factor> ::= <number> | "(" <expr> ")"
<number> ::= "1" | "1" <number>

Strings that conform to <expr> include:

  • 1111+111 representing 1111+111.
  • (1+1)*(1+1) representing (1+1)\times(1+1).
  • (11+(1+1)*(1+1))+1 representing (11+(1+1)\times(1+1))+1.

Strings that do not conform to <expr> include:

  • (1+1)(1+1)
  • 1+2
  • 1-1
  • 1/1
  • )1(
  • 1++1
  • +1
  • (+1)
  • 1*+1

Constraints

  • 1 \le N \le 2000
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N

Output

Print a solution.

Sample Input 1

9

Sample Output 1

(1+1+1)*(1+1+1)

Expressions whose value is 9 include:

  • (1+1+1)*(1+1+1)
  • 1+1+1+1+1+1+1+1+1
  • (1+1)*(1+1)*(1+1)+1

Among them, a shortest is (1+1+1)*(1+1+1).

Sample Input 2

11

Sample Output 2

11

Sample Input 3

403

Sample Output 3

1+(1+1+1)*(1+11+11+111)