MinProduct
SRM 720 · 2017-07-25 · by lg5293
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.
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.
{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}
9
9
Returns: 12345678987654321
{1,0,0,0,1,0,0,5,3,2}
9
3
Returns: 36556078253
Submissions are judged against all 72 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MinProduct with a public method long long findMin(vector<int> amount, int blank1, int blank2) · 72 test cases · 2 s / 256 MB per case