AIOC Banner

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.

Sample Input

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:

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-2024

Contact: training@orac.amt.edu.au
Page generated: 29 March 2024,  1:02am AEDT