ReProduct
TCO19 Round 4 · 2019-04-15 · by misof
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.
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.
{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
Submissions are judged against all 155 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ReProduct with a public method long long minimize(vector<int> base, int goal) · 155 test cases · 2 s / 256 MB per case