fork download
copy 
  1. object Main extends App {
  2.  
  3. object Q1119{
  4.  
  5.   val sqCache = (1 to 1000).map(n => (Tuple2(n*n, true))).toMap
  6.   def isSq(n:Int):Boolean = {
  7.     sqCache.getOrElse(n, false)
  8.   }
  9.  
  10.   def helper(cand:List[Int], digits:List[Int], c:List[Int]):List[Int] = {
  11.     cand match {
  12.       case Nil => Nil // たして平方数となる数が無いので Nil
  13.       case x::xs => {
  14.         val d = explore(x, digits.filter(v=>{v!=x}), c)
  15.         // 題意を満す(=Nil でない)解があればそれを返し、
  16.         // なければ次の候補を探索
  17.         if (d!=Nil) {d} else helper(xs, digits, c)
  18.       }
  19.     }
  20.   }
  21.   def explore(me:Int, digits:List[Int], c:List[Int]):List[Int] = {
  22.     if (digits==Nil){
  23.       // 1 から nまでの数を全て使い切れたので、
  24.       // 先頭と最終を足しても平方数ならそれが解。
  25.       // 平方数でなければ Nil とする
  26.       if(isSq(me + c.last)){me::c} else {Nil}
  27.     } else {
  28.       // たして平方数となる候補を抽出して、
  29.       // 題意をみたす切り方ができるか探索
  30.       val candidates = digits.filter(n => isSq(me+n))
  31.       helper(candidates, digits, me::c)
  32.     }
  33.   }
  34.  
  35.  
  36.   def solve(n:Int = 2):Tuple2[Int, List[Int]] = {
  37.     val q = explore(1, (2 to n).toList, Nil)
  38.     if (q!=Nil){Tuple2(n, q)} else {solve(n+1)}
  39.   }
  40. }
  41.  
  42. val ret = Q1119.solve()
  43. println("%d: %s".format(ret._1, ret._2.reverse.mkString(",")))
  44. }
Time limit exceeded #stdin #stdout 5s 1024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Vy4b1M
language:
Scala (scala 2.12.8)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!