Monodigital Expression
Time limit2sMemory limit128 MB
Compute, for repeated digit K and concatenations plus arithmetic operators, the minimum number of K digits needed to build each queried integer (or report NO if it exceeds 8).
- Level
Medium6 of 10
- Topics
- Dynamic programming, Math, Brute force
- Solved
- No attempts yet
Problem
The digit K is one of the digits from 1 to 9. An expression for a positive integer X that uses several copies of the digit K and only the four arithmetic operations +, -, *, and / is called a K-expression of X.
Parentheses may be used in expressions. Division uses only the integer quotient. You may also concatenate several copies of K into one number. For example, when K = 5, the numbers 5, 55, and 555 may be used.
The length of a K-expression is the number of copies of K used in it. Given K, find the shortest possible K-expression length for each requested positive integer.
Input
The first line contains the digit K.
The second line contains the number n of positive integers whose shortest expression lengths must be found. 1 <= n <= 1,000.
Each of the next n lines contains one positive integer a. For every a, 1 <= a <= 32,000.
Output
For each input integer, output the minimum length of a possible K-expression, one per line, in input order.
If the minimum length is greater than 8, or if the integer cannot be expressed with length at most 8, output NO.