MagicalMarvelousTour.scala

import java.io.{FileReader, BufferedReader}

object MagicalMarvelousTour extends App {
  val input = new BufferedReader(new FileReader("A-sample.in"))
  val T: Int = input.readLine().toInt
  for (t <- 0 until T) {
    val Array(n, p, q, r, s) = input.readLine().split(' ').map(_.toInt)

//    ((i * p + q) MOD r + s)
    val probability = calc((for (i <- (0 until n)) yield {
      ((i * p + q) % r) + s
    }).toList.map(_.toLong))
    println(f"Case #${t + 1}: ${probability}%2.10f")
  }

  def calc(list: List[Long]): Double = {
    val accumulated = list.scanLeft(0L)(_ + _).tail
    if (list.length == 2) {
      return ((accumulated.last - Math.max(list(0), list(1))) / accumulated.last.toDouble)
    }
    val start = (accumulated.last / 3)
    val end = start * 2

    var s = accumulated.lastIndexWhere(_ <= start)
    if (s < 0) s = 0
    var e = accumulated.lastIndexWhere(_ <= end)
    if (e < 1) e = 1

    var probability = 0d

    val d = 1

    for (i <- (s - d) to (s + d)) yield {
      for (j <- (e - d) to (e + d)) yield {
        val sliced = slice(list, accumulated, i, j)
        val tmp = (accumulated.last - sliced.map(_.sum).max) / accumulated.last.toDouble
        probability = Math.max(probability, tmp)
      }
    }
    probability
  }

  def slice(list:List[Long], accumulated: List[Long], start: Int, end: Int): List[List[Long]] = {
    val f = list.take(start + 1)
    val m = list.slice(start + 1, end + 1)
    val l = list.takeRight(accumulated.length - end - 1)
    return List(f, m, l)
  }

}