MagicalMarvelousTour.scala

object MagicalMarvelousTour extends App {

  def winningProbability(n: Int, p: Int, q: Int, r: Int, s: Int): Double = {

    val as = for {
      i <- 0 until n
    } yield ((i * p + q) % r + s)
    
    val ss = (List.empty[Int] /: as) {
      case (Nil, a)     => a :: Nil
      case (s :: ts, a) => (s + a) :: s :: ts
    }.reverse
    
    val partitions = for {
      x <- 0 until as.size
      y <- x until as.size
    } yield (x, y)

    def cut(x: Int, y: Int): (Int, Int) = {
      val partitions = for {
        (i, j) <- Vector((0, x), (x, y), (y, as.size))
      } yield as.slice(i, j).sum
      (partitions.max, partitions.sum)
    }

    val (x, y) = partitions minBy { case (x, y) => cut(x, y)._1 }

    val (max, sum) = cut(x, y)
    (sum - max) / sum.toDouble

  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      val Array(n, p, q, r, s) = lineIn.next() split ' ' map (_.toInt)
      lineOut(f"Case #$i: ${winningProbability(n, p, q, r, s)}%1.10f")
    }

  val writer = new java.io.PrintWriter("a.small.out")
  try {
    process(io.Source.fromFile("A-small-practice.in").getLines) { s =>
      writer.println(s)
      writer.flush()
    }
  } finally {
    writer.flush(); writer.close()
  }

}

MagicalMarvelousTourTest.scala

import org.scalatest._

import MagicalMarvelousTour._

class MagicalMarvelousTourTest extends FunSuite with ShouldMatchers {

  test("sample #2") {
    winningProbability(10, 17, 1, 7, 1) should === (0.6111111111 +- 1e-9)
  }
  
  test("sample #1") {
    winningProbability(1, 1, 1, 1, 1) should === (0.0 +- 1e-9)
  }
  
  test("sample #3") {
    winningProbability(2, 100, 100, 200, 1) should === (0.0098039216 +- 1e-9)
  }

  test("sample case for small case") {
    val input = """7
1 1 1 1 1
10 17 1 7 1
2 100 100 200 1
20 17 3 23 100
10 999999 999999 1000000 1000000
2 1 1 1 1
3 1 99 100 1""".lines

    val expected = """Case #1: 0.0000000000
Case #2: 0.6111111111
Case #3: 0.0098039216
Case #4: 0.6471920290
Case #5: 0.6000006000
Case #6: 0.5000000000
Case #7: 0.0291262136""".lines

    lineComparison(input, expected)
  }

  ignore("full small case") {
    val input = io.Source.fromFile("A-small-practice.in").getLines()
    val expected = io.Source.fromFile("a.small.out.ref").getLines()

    lineComparison(input, expected)
  }

  ignore("full large case") {
    val input = io.Source.fromFile("A-large-practice.in").getLines()
    val expected = io.Source.fromFile("a.large.out.ref").getLines()

    lineComparison(input, expected)
  }

  def lineComparison(input: Iterator[String], expected: Iterator[String]) {
    process(input) { s =>
      for (line <- s.lines) assert(line.trim === expected.next().trim)
    }
    assert(expected.hasNext === false, "Finished too fast.")
  }

}