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

**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 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.

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

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

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

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

© Australian Mathematics Trust 2001-2021

Page generated: 1 December 2021, 10:47am AEDT