Advertisement
Guest User

Untitled

a guest
Sep 19th, 2014
246
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Scala 2.39 KB | None | 0 0
  1. import scala.Array.canBuildFrom
  2. import scala.collection.mutable.ArrayBuffer
  3.  
  4. object test extends App {
  5.   val MAX = 10000000
  6.   val is = Array.fill(MAX)(true)
  7.   is(0) = false
  8.   is(1) = false
  9.   for (i <- 2 until MAX; if (i.toLong * i < MAX && is(i)))
  10.     for (j <- (i + i).until(MAX, i)) is(j) = false
  11.  
  12.   val primes = (2 until MAX).filter(i => is(i))
  13.   val Array(n, k, l) = readLine.split(" ").map(_.toInt)
  14.   val threshold = 10 - l
  15.   var ansA: Array[Int] = Array()
  16.   val ansList: ArrayBuffer[List[Int]] = new ArrayBuffer[List[Int]]
  17.  
  18.   def isok(a: Array[Int]): Boolean = {
  19.     val min = if (a(0) == -1) 1 else 0
  20.     var fail = 0
  21.     var cnt = 0
  22.     var list: List[Int] = Nil
  23.     for (i <- min to 9) {
  24.       var tmp = 0;
  25.       for (j <- 0 until n)
  26.         if (a(j) == -1) tmp = tmp * 10 + i
  27.         else tmp = tmp * 10 + a(j)
  28.  
  29.       if (!is(tmp)) fail += 1
  30.       else {
  31.         cnt += 1
  32.         list = tmp :: list
  33.       }
  34.       if (a.toList == List(1, 1, 3)) println(list)
  35.       if (cnt == l) {
  36.         ansList += list
  37.         return true
  38.       }
  39.       if (min == 1 && fail > threshold - 1 || min == 0 && fail > threshold) return false
  40.     }
  41.     true
  42.   }
  43.  
  44.   def dfs(a: Array[Int], digit: Int, t: Int, cnt: Int) {
  45.     if (t == n) {
  46.       if (cnt == 0 && isok(a)) {
  47.         ansA = a
  48.       }
  49.     } else {
  50.       if (cnt > 0) {
  51.         if (digit != -1) {
  52.           if (a(t) == digit) {
  53.             a(t) = -1
  54.             dfs(a, digit, t + 1, cnt - 1)
  55.             a(t) = digit
  56.           }
  57.         } else {
  58.           val tmp = a(t)
  59.           a(t) = -1
  60.           dfs(a, tmp, t + 1, cnt - 1)
  61.           a(t) = tmp
  62.         }
  63.       }
  64.       dfs(a, digit, t + 1, cnt)
  65.     }
  66.   }
  67.  
  68.   val a = Array.fill(n)(0)
  69.   def convert(a: Array[Int], x: Int, t: Int) {
  70.     if (x > 0) {
  71.       a(t) = x % 10
  72.       convert(a, x / 10, t - 1)
  73.     }
  74.   }
  75.  
  76.   def length(x: Int, acc: Int): Int = if (x == 0) acc else length(x / 10, acc + 1)
  77.  
  78.   def doit(i: Int): Int = {
  79.     if (i >= primes.length || length(primes(i), 0) > n) -1
  80.     else if (length(primes(i), 0) < n) doit(i + 1)
  81.     else {
  82.       convert(a, primes(i), n - 1)
  83.       dfs(a, -1, 0, k)
  84.       if (ansA.length > 0) {
  85.         primes(i)
  86.       } else doit(i + 1)
  87.     }
  88.   }
  89.  
  90.   val ans = doit(0)
  91.   //  println(ans)
  92.   if (ans != -1) {
  93.     println(ansList.result.map(_.reverse).sortBy(list => list.foldLeft("")(_ + _)).head.mkString(" "))
  94.   }
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement