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:
New Year Tree
Interactive LowerBound
Bacterial Melee
Little Artem and Grasshopper
The Brand New Function
PolandBall and Gifts
Fox and Card Game
Third Month Insanity
Suns and Rays
Network Configuration
Graph Coloring
Promocodes with Mistakes
Grandfather Dovlet’s calculator
TOF
Inversions problem
New Year and the Mallard Expedition
Happy Cactus
Bribes
Fibonacci-ish
Social Network
Count The Blocks
The Values You Can Make
Half-plane intersection - S&I Algorithm in O(Nlog N)
Bob and stages
Packmen
Bits And Pieces
Cinema
Euclidean algorithm for computing the greatest common divisor
Salazar Slytherin's Locket
New Year Letter
Divisor Tree
Sieve of Eratosthenes Having Linear Time Complexity