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:
The Holmes Children
Aztec Catacombs
Sereja and the Arrangement of Numbers
Foo Fighters
Chinese Remainder Theorem
Fox And Polygon
Businessmen Problems
Arson In Berland Forest
Prüfer code
R3D3’s Summer Adventure
Rectangles and Square
Letters and Question Marks
Nastya and Strange Generator
Little Artem and Matrix
Playing with Permutations
Integration by Simpson's formula
Submask Enumeration
Maximum Distance
Paint the Numbers
New Year and the Acquaintance Estimation
Primal Sport
Constrained Tree
Civilization
New Year and Old Property
Tape
Satanic Panic
Kuroni and Simple Strings
Merging Two Decks
Heavy-light decomposition
Suffix Automaton
Orchestra
Yet Another Array Queries Problem