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:
Pokermon League challenge
Birthday
Pie Rules
Largest Submatrix 3
The Inclusion-Exclusion Principle
Intersecting Subtrees
Alice and Hairdresser
Grandfather Dovlet’s calculator
Field expansion
Magic Stones
Double Elimination
Packets
Another One Bites The Dust
To Play or not to Play
Sum of Odd Integers
Closest Equals
Fox And Dinner
Break Up
Basic Geometry
Encoding
Optimal schedule of jobs given their deadlines and durations
Sieve of Eratosthenes
Aquarium decoration
Finding the Eulerian path in $O(M)$
Limericks
Challenging Balloons
Robbers' watch
Context Advertising
Interesting Array
New Year and Castle Construction
Kuroni the Private Tutor
Nastya and Time Machine