For a given positive integer $m$, a positive number is called a $m$-number if the product of its digits is $m$. For example, the beginning of a series of $24$-numbers are as follows: $38$, $46$, $64$, $83$, $138$, $146$, $164$, $183$, $226$ …
You are given a positive integer $m$ and $k$. Print $k$-th among $m$-numbers if all $m$-numbers are sorted in ascending order.Input
A single line of input contains two integers $m$ and $k$ ($2 \le m \le 10^9$, $1 \le k \le 10^9$).Output
Print the desired number — $k$-th among all $m$-numbers if $m$-numbers are sorted in ascending order. If the answer does not exist, print -1.Examplesinput
24 9
output
226
input
24 1
output
38
input
5040 1000000000
output
111121111315213227111
input
2020 2020
output
-1
Solution:
private fun readLn() = readLine()!! // string line private fun readInt() = readLn().toInt() // single int private fun readLong() = readLn().toLong() // single long private fun readDouble() = readLn().toDouble() // single double private fun readStrings() = readLn().split(" ") // list of strings private fun readInts() = readStrings().map { it.toInt() } // list of ints private fun readLongs() = readStrings().map { it.toLong() } // list of longs private fun readDoubles() = readStrings().map { it.toDouble() } // list of doubles fun main(args: Array<String>) { var (m, k) = readInts() var cnt = IntArray(10) for (i in 2..7) { while (m % i == 0) { m /= i cnt[i] += 1 } } if (m > 1) { println("-1") return } var allow = minOf(50000,2000000 / (cnt[2] + 1) / (cnt[3] + 1) / (cnt[5] + 1) / (cnt[7] + 1)) var dp = Array(allow) { Array(cnt[2] + 1) { Array(cnt[3] + 1) { Array(cnt[5] + 1) {IntArray(cnt[7] + 1) {0} } } } } dp[0][0][0][0][0] = 1 for (i in 0 until dp.size - 1) { for (k2 in 0..cnt[2]) { for (k3 in 0..cnt[3]) { for (k5 in 0..cnt[5]) { for (k7 in 0..cnt[7]) { var ft = dp[i][k2][k3][k5][k7] if (ft == 0) { continue } for (d in 1..9) { var n2 = k2 var n3 = k3 var n5 = k5 var n7 = k7 var x = d while (x % 2 == 0) { x /= 2 n2++ } while (x % 3 == 0) { x /= 3 n3++ } while (x % 5 == 0) { x /= 5 n5++ } while (x % 7 == 0) { x /= 7 n7++ } if (n2 <= cnt[2] && n3 <= cnt[3] && n5 <= cnt[5] && n7 <= cnt[7]) { dp[i + 1][n2][n3][n5][n7] = minOf(k, dp[i + 1][n2][n3][n5][n7] + ft) } } } } } } } for (len in 1 until dp.size) { var k2 = cnt[2] var k3 = cnt[3] var k5 = cnt[5] var k7 = cnt[7] var cur = dp[len][k2][k3][k5][k7] if (k > cur) { k -= cur continue } for (i in 0 until len) { for (d in 1..9) { var n2 = k2 var n3 = k3 var n5 = k5 var n7 = k7 var x = d while (x % 2 == 0) { x /= 2 n2-- } while (x % 3 == 0) { x /= 3 n3-- } while (x % 5 == 0) { x /= 5 n5-- } while (x % 7 == 0) { x /= 7 n7-- } if (n2 >= 0 && n3 >= 0 && n5 >= 0 && n7 >= 0) { var cur = dp[len - i - 1][n2][n3][n5][n7] if (cur < k) { k -= cur } else { print(d) k2 = n2 k3 = n3 k5 = n5 k7 = n7 break } } } } println() break } }
Related posts:
Catalan Numbers
World of Darkraft - 2
Suffix Automaton
Bacterial Melee
Optimal Polygon Perimeter
Topological Sorting
K-th order statistic in O(N)
Spy Syndrome 2
Run for beer
Sieve of Eratosthenes
Finding strongly connected components - Building condensation graph
Petr and a Combination Lock
Preparing for the Contest
Party
Number of paths of fixed length / Shortest paths of fixed length
Flights
Om Nom and Spiders
Maximum flow - Dinic's algorithm
To Hack or not to Hack
Montgomery Multiplication
Matching Names
Xors on Segments
Dream Team
Games on arbitrary graphs
Delaunay triangulation and Voronoi diagram
Bear and Polynomials
Packets
Meaningless Operations
XOR Equation
Linear Congruence Equation
Tom Riddle's Diary
PolandBall and Hypothesis