NewOperator | Topcoder Archive

Problem Statement

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.

Definition

Class:: NewOperator
Method:: minimumCount
Parameters:: int, int
Returns:: int
Method signature:: int minimumCount(int x, int goal)
(be sure your method is public)

Constraints

x will be between 1 and 1,000,000, inclusive.
goal will be between 1 and 2,000,000,000, inclusive.

Examples

```
13
```
```
13
```
```
Returns: 0
```
"x" is a valid expression that evaluates to 13.
```
374
```
```
465
```
```
Returns: 1
```
"(x@x)" is a valid expression. For x=374 its value is 5 * (7*4*3) + 3 * (3+7+4) + 3 = 465.
```
374
```
```
469
```
```
Returns: 2
```
"(x@(x@x))" evaluates to 469.
```
374
```
```
659
```
```
Returns: 2
```
"((x@x)@x)" evaluates to 659. Note that the operator is not associative.
```
374
```
```
1024
```
```
Returns: 8
```
```
654321
```
```
12
```
```
Returns: 10
```
```
654321
```
```
1234567
```
```
Returns: -1
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.