fork download
copy 
  1. object Main extends App {
  2.  
  3.   val sqCache = (1 to 1000).map(n => (Tuple2(n*n, true))).toMap
  4.   def isSq(n:Int):Boolean = {
  5.     sqCache.getOrElse(n, false)
  6.   }
  7.  
  8.   def helper(cand:List[Int], digits:List[Int], c:List[Int]):List[Int] = {
  9.     cand match {
  10.       case Nil => Nil // たして平方数となる数が無いので Nil
  11.       case x::xs => {
  12.         val d = explore(x, digits.filter(v=>{v!=x}), c)
  13.         // 題意を満す(=Nil でない)解があればそれを返し、
  14.         // なければ次の候補を探索
  15.         if (d!=Nil) {d} else helper(xs, digits, c)
  16.       }
  17.     }
  18.   }
  19.   def explore(me:Int, digits:List[Int], c:List[Int]):List[Int] = {
  20.     if (digits==Nil){
  21.       // 1 から nまでの数を全て使い切れたので、
  22.       // 先頭と最終を足しても平方数ならそれが解。
  23.       // 平方数でなければ Nil とする
  24.       if(isSq(me + c.last)){me::c} else {Nil}
  25.     } else {
  26.       // たして平方数となる候補を抽出して、
  27.       // 題意をみたす切り方ができるか探索
  28.       val candidates = digits.filter(n => isSq(me+n))
  29.       helper(candidates, digits, me::c)
  30.     }
  31.   }
  32.  
  33.  
  34.   def solve(n:Int = 2):Tuple2[Int, List[Int]] = {
  35.     val q = explore(1, (2 to n).toList, Nil)
  36.     if (q!=Nil){Tuple2(n, q)} else {solve(n+1)}
  37.   }
  38. }
  39.  
  40. val ret = Main.solve()
  41. println("%d: %s".format(ret._1, ret._2.reverse.mkString(",")))
  42.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/opt/scala/bin/scalac: line 50: /dev/null: Permission denied
Main.scala:40: error: expected class or object definition
val ret = Main.solve()
^
Main.scala:41: error: expected class or object definition
println("%d: %s".format(ret._1, ret._2.reverse.mkString(",")))
^
two errors found
spoj: The program compiled successfully, but Main.class was not found.
      Class Main should contain method: def main(args: Array[String]).
stdout
copy 
Standard output is empty
https://ideone.com/j02znM
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!