MagicalMarvelousTour.scala

MagicalMarvelousTour.scala

package magicaltour

object Main {

  def solve(n: Int, p: Int, q: Int, r: Int, s: Int): String = {
    def getMiddle(remain: Seq[Int]): Double = {
      val oneOfThird = remain.sum / 3
      def getSmaller(remain: Seq[Int], aggregate: Int = 0): (Int, Seq[Int]) = remain match {
        case Nil => (aggregate, remain)
        case remain if (aggregate == 0) => getSmaller(remain.tail, aggregate + remain.head)
        case remain if (aggregate + remain.head == oneOfThird) => (aggregate + remain.head, remain.tail)
        case remain if (aggregate + remain.head > oneOfThird) => (aggregate, remain)
        case _ => getSmaller(remain.tail, aggregate + remain.head)
      }
      def cases(left: Int, middle: Seq[Int], right: Int): Seq[Int] = middle match {
        case Nil                       => List(left, 0, right)
        case middle if middle.size < 2 => List(left, middle.sum, right)
        case _ => {
          val middleNum = middle.tail.init.sum
          val last = middle.last
          val cases = Seq(Seq(left, middle.head + middleNum + last, right), Seq(left, middle.head + middleNum, last + right), Seq(left + middle.head, middleNum + last, right), Seq(left + middle.head, middleNum, last + right))
          cases.sortBy(r => (r.max)).head
        }
      }
      val (left, rights) = getSmaller(remain)
      val (right, middle) = getSmaller(rights.reverse)
      val result = cases(left, middle.reverse, right)
//      println(remain, result)
      1 - result.max.toDouble / remain.sum
    }
    val t = (0 until n).map(i => ((i * p + q) % r) + s).toList
    val result = getMiddle(t)
//    println(f"$t $result")
    "%.10f".format(result)
  }

  def main(args: Array[String]) {
    test()
  }

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

  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)
      val answer = solve(n, p, q, r, s)
      lineOut(s"Case #$i: $answer")
    }
  }

  def test() {
    //    println(solve(1, 1, 1, 1, 1) == "0.0000000000")
    //    println(solve(10, 17, 1, 7, 1) == "0.6111111111")
    //    println(solve(2, 100, 100, 200, 1) == "0.0098039216")
    //    println(solve(20, 17, 3, 23, 100) == "0.6471920290")
    //    println(solve(10, 999999, 999999, 1000000, 1000000) == "0.6000006000")
    //    println(solve(2, 1, 1, 1, 1) == "0.5000000000")
    //    println(solve(3, 1, 99, 100, 1) == "0.0291262136")
    //    println(solve(10, 25, 30, 11, 20) == "0.6120000000")
    //    println(solve(5, 10, 24, 29, 21) == "0.5944444444")
    //    println(solve(2, 100, 100, 200, 1) == "0.0098039216")
    //    println(solve(5, 6, 21, 7, 16) == "0.6020408163")
    //    println(solve(4, 11, 11, 21, 1) == "0.5333333333")
    println(solve(999999, 1000000, 999999, 1000000, 1000000) == "0.6666666667")
  }

}

https://code.google.com/codejam/contest/3024486/dashboard