SmoothingWindow.scala

import java.io.FileOutputStream
import scala.io.Source

object SmoothingWindow {
  def solve(in: Seq[String]) = {
    val Array(n,k) = in.head.split(" ").map(_.toInt)
    val s = in(1).split(" ").map(_.toInt)
    
    val seq = Array.fill[Int](n)(0)
    (0 until n - k).foreach(i => seq(i + k) = seq(i) + s(i + 1) - s(i)) //(k until n).foreach(i => seq(i) = seq(i - k ) + s(i - k + 1) - s(i - k))
    
    val groups = seq.zipWithIndex.groupBy(_._2 % k).map(_._2.map(_._1))

    val intervals = groups.map(i => i.max - i.min)
    val L = intervals.max
    val extra = intervals.map(L - _).sum

    val Q = s(0) + groups.map(_.min).sum
    val q = (Q % k + k) % k

    if(extra - q < 0) L + 1 else L
  }



  def main(args: Array[String]): Unit = {
    val INPUT = "B-large-practice.in"
    val OUTPUT = INPUT.takeWhile(_ != '.') + ".out"
    val isConsole = false

    val itr = Source.fromFile(INPUT).getLines()
    val stream = if (isConsole) Console.out else new FileOutputStream(OUTPUT)
    try {
      Console.withOut(stream) {
        val sets = itr.next().toInt
        (1 to sets).foreach { set =>
          val seq = Seq(itr.next(),itr.next())
          println(f"Case #$set: ${solve(seq)}")
        }
      }
    } finally {
      stream.flush()
      if (!isConsole) stream.close()
    }
  }
}