MinProduct | Topcoder Archive

Problem Statement

You are given an array amount with exactly 10 elements, where the i-th element denotes the number of copies of the digit i you have.

You would like to construct two nonnegative integers A and B. The base-10 representation of A must have exactly blank1 digits. The base-10 representation of B must have exactly blank2 digits. It is allowed for A and B to contain leading zeros. In addition, the total number of appearances of digit i in the numbers A and B must be at most amount[i]. It's guaranteed that the sum of amount is at least blank1 + blank2.

Among all valid pairs (A, B), find the one for which A * B is minimal. Return the smallest possible value of the product A * B.

Definition

Class:: MinProduct
Method:: findMin
Parameters:: int[], int, int
Returns:: long
Method signature:: long findMin(int[] amount, int blank1, int blank2)
(be sure your method is public)

Constraints

amount will have exactly 10 elements.
Each element of amount will be between 0 and 20.
blank1, blank2 will be between 1 and 9, inclusive.
The sum of elements in amount will be at least blank1 + blank2.

Examples

```
{0,1,1,2,1,1,0,0,0,0}
```
```
2
```
```
3
```
```
Returns: 3042
```
In this case, we have the numbers {1,2,3,3,4,5}. A must consist of 2 digits, and B must consist of 3 digits. In this case, one optimal solution is to let A = 13 and B = 234. Then, A * B = 3042. We can show that no other way of assigning digits will give a strictly smaller value A * B.
```
{1,1,1,1,1,1,1,1,1,1}
```
```
1
```
```
8
```
```
Returns: 0
```
We can let A = 0, B = 98765432.
```
{1,3,0,0,0,0,0,0,0,0}
```
```
2
```
```
2
```
```
Returns: 11
```
It is allowed for A or B to have leading zeros.

{0,20,20,20,20,20,20,20,20,20}

Returns: 12345678987654321

{1,0,0,0,1,0,0,5,3,2}

Returns: 36556078253

{0,0,0,0,0,0,0,0,0,18}

Returns: 99999998900000001

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.