Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import scala.Array.canBuildFrom
- import scala.collection.mutable.ArrayBuffer
- object test extends App {
- val MAX = 10000000
- val is = Array.fill(MAX)(true)
- is(0) = false
- is(1) = false
- for (i <- 2 until MAX; if (i.toLong * i < MAX && is(i)))
- for (j <- (i + i).until(MAX, i)) is(j) = false
- val primes = (2 until MAX).filter(i => is(i))
- val Array(n, k, l) = readLine.split(" ").map(_.toInt)
- val threshold = 10 - l
- var ansA: Array[Int] = Array()
- val ansList: ArrayBuffer[List[Int]] = new ArrayBuffer[List[Int]]
- def isok(a: Array[Int]): Boolean = {
- val min = if (a(0) == -1) 1 else 0
- var fail = 0
- var cnt = 0
- var list: List[Int] = Nil
- for (i <- min to 9) {
- var tmp = 0;
- for (j <- 0 until n)
- if (a(j) == -1) tmp = tmp * 10 + i
- else tmp = tmp * 10 + a(j)
- if (!is(tmp)) fail += 1
- else {
- cnt += 1
- list = tmp :: list
- }
- if (a.toList == List(1, 1, 3)) println(list)
- if (cnt == l) {
- ansList += list
- return true
- }
- if (min == 1 && fail > threshold - 1 || min == 0 && fail > threshold) return false
- }
- true
- }
- def dfs(a: Array[Int], digit: Int, t: Int, cnt: Int) {
- if (t == n) {
- if (cnt == 0 && isok(a)) {
- ansA = a
- }
- } else {
- if (cnt > 0) {
- if (digit != -1) {
- if (a(t) == digit) {
- a(t) = -1
- dfs(a, digit, t + 1, cnt - 1)
- a(t) = digit
- }
- } else {
- val tmp = a(t)
- a(t) = -1
- dfs(a, tmp, t + 1, cnt - 1)
- a(t) = tmp
- }
- }
- dfs(a, digit, t + 1, cnt)
- }
- }
- val a = Array.fill(n)(0)
- def convert(a: Array[Int], x: Int, t: Int) {
- if (x > 0) {
- a(t) = x % 10
- convert(a, x / 10, t - 1)
- }
- }
- def length(x: Int, acc: Int): Int = if (x == 0) acc else length(x / 10, acc + 1)
- def doit(i: Int): Int = {
- if (i >= primes.length || length(primes(i), 0) > n) -1
- else if (length(primes(i), 0) < n) doit(i + 1)
- else {
- convert(a, primes(i), n - 1)
- dfs(a, -1, 0, k)
- if (ansA.length > 0) {
- primes(i)
- } else doit(i + 1)
- }
- }
- val ans = doit(0)
- // println(ans)
- if (ans != -1) {
- println(ansList.result.map(_.reverse).sortBy(list => list.foldLeft("")(_ + _)).head.mkString(" "))
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement