Multiple With the Fewest Digit Types
Time limit1sMemory limit128 MB
Given N up to 30000, find the smallest positive multiple of N that uses the fewest distinct decimal digits.
- Level
Hard8 of 10
- Topics
- BFS, Math, Combinatorics, Graph
- Solved
- No attempts yet
Problem
Among the positive multiples of a natural number N, find a number whose decimal representation uses as few different digits as possible.
For example, when N = 125, the multiple 250 uses three different digits: 2, 5, and 0. Another multiple, 500, uses only two different digits: 5 and 0. Thus 500 is one of the multiples that can be written with fewer digit types.
Given N, first minimize the number of distinct digits used. If several positive multiples achieve that minimum, output the smallest such value.
Input
The first line contains a natural number N.
N is at most 30,000.
Output
Print the smallest positive multiple of N among the multiples that use the minimum possible number of distinct digits.