 # Problem: Building Integers

Want to try solving this problem? You can submit your code online if you log in or register.

## Building Integers

Input File: buildin.txt
Output File: buildout.txt
Time Limit: 0.4 seconds

As a year three homework assignment, your younger sister has been asked to build numbers using only the symbols + x ( ) and 1. However, being the technologically aware child that she is, she has written a computer program to do her homework for her.

After looking over her shoulder, you begin to wonder how to create any given number using the least number of such symbols. Eventually, you too decide to write a computer program to solve this new problem.

Numbers can be built using only the symbols + x ( ) and 1. The order convention must be followed (i.e., multiplication is performed before addition unless the brackets tell you otherwise). You may place digits next to each other to form larger numbers such as 11 and 111.

Your task is to work out the least number of symbols required to create any given integer.

### Input

Input will consist of a list of integers, one on each line. Each integer will be between 1 and 2000 inclusive. The list will be terminated by the integer 0.

### Output

For each integer in the input list, you must output a way of creating the given integer using the smallest number of symbols. If there is more than one smallest way of creating it, any such solution will do. Your output for the given integer should be a single line of the form

given integer = method of construction

as illustrated in the sample output. The output should contain no spaces. There should be no output for the final 0 in the input list.

It is guaranteed that no construction will require more than 40 symbols.

```4
23
242
0
```

### Sample Output

```4=1+1+1+1
23=11+11+1
242=(11+11)*11
```

### Scoring

For each line of the input file:

• A mathematically correct expansion that uses the minimum number of symbols will score 100%.
• A mathematically correct expansion that uses more symbols than necessary will score 100% minus 15% for each extra symbol used, down to a minimum score of 10%.
• A mathematically incorrect expansion will score 0%.

For instance, an expansion of `23=11*(1+1)+1` will score 55%, and an expansion of `23=11*(1+1)` will score 0%.

Privacy statement
`Page generated: 15 November 2019,  5:53am AEDT`