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:
Power Tree
Happy Cactus
Arkady and a Nobody-men
Tree-Tac-Toe
Egor and an RPG game
Balanced bracket sequences
And after happily lived ever they
Read Time
Walk on Matrix
Race
Grid Sort
Gotta Go Fast
Infinite Path
Learning and Improving Algorithm through contests - Antti Laaksonen
Declined Finalists
Bags and Coins
Dreamoon Likes Strings
Wise Men (Hard Version)
Limak and Shooting Points
Potions Homework
Network Configuration
Foo Fighters
Developing Game
Breadth-first search
Graph Reconstruction
The Door Problem
Ramesses and Corner Inversion
Adding Digits
Strong Orientation
Points on Line
Perfect Security
Fountains