ReProduct | Topcoder Archive

Problem Statement

Each of the digits 0 through 9 has a value that is in {0, 1, 2}. At least one of the digits has value 0. These values are given: the value of digit x is base[x].

For any bigger positive integer n, the value of n is one greater than the value of p(n), where p is the product of digits of n.

You are given the number goal. Return the smallest nonnegative integer with value goal. You may assume that for any valid input the output value exists and does not exceed 10^18.

Definition

Class:: ReProduct
Method:: minimize
Parameters:: int[], int
Returns:: long
Method signature:: long minimize(int[] base, int goal)
(be sure your method is public)

Constraints

base will contain exactly 10 elements.
Each element in base will be between 0 and 2, inclusive.
The smallest element in base will be 0.
goal will be between 0 and 11, inclusive.

Examples

```
{0,1,1,1,1,1,1,1,1,1}
```
```
2
```
```
Returns: 11
```
As given, the number 0 has value 0. As given, each of the numbers 1-9 has value 1. The number 10 has value 1 (because the number 1*0 = 0 has value 0). The number 11 has value 2 (because the number 1*1 = 1 has value 1). Thus, 11 is the smallest number with value 2.
```
{0,0,0,0,0,0,0,0,0,0}
```
```
3
```
```
Returns: 39
```
We have value(39) = 1 + value(27) = 2 + value(14) = 3 + value(4) = 3, and no smaller number has value 3.
```
{2,0,0,0,0,0,0,0,0,0}
```
```
2
```
```
Returns: 0
```
```
{2,2,2,2,2,2,2,2,0,2}
```
```
1
```
```
Returns: 18
```
```
{2,1,2,2,1,1,1,0,1,0}
```
```
6
```
```
Returns: 268
```

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.