Given a positive integer N, we may define the following unary functions:
- sum(N) is the sum of the decimal digits of N.
- prod(N) is the product of the decimal digits of N.
- prod3(N) is the product of the three largest decimal digits of N.
If N has
less than three digits, prod3(N)=prod(N).
- smallest(N) is the smallest decimal digit of N.
- first(N) is the first (most significant) decimal digit of N.
Now we may define the binary operator @ as follows:
- X@Y = 5 * prod3(X) + first(X) * sum(Y) + smallest(Y)
Examples:
- sum(47) = 4+7 = 11
- prod(2322) = 2*3*2*2 = 24
- prod3(2322) = 3*2*2 = 12
- prod3(47) = 4*7 = 28
- smallest(427) = 2
- first(427) = 4
- 12034@217 = 5 * (4*3*2) + 1 * (2+1+7) + 1 = 131
We will be interested in expressions that use only the operator @ and a single variable
x.
Valid expressions are defined using the following rules:
- x is a valid expression.
- If E and F are valid expressions, then (E@F) is a valid
expression.
- Any string that can not be formed using the rules above is not a valid expression.
You are given an int x containing the value of the variable x used
above, and an
int goal. Find the shortest valid expression that evaluates to goal, and
return
the number of operators it contains. If no such expression exists, return -1 instead.
|