DataPacking.scala

import scala.annotation.tailrec

object Main {

  def solve(input:List[Int], diskCapacity:Int):Int = {
    @tailrec
    def subroutine(input:List[Int], acc:Int) : Int = {
      if (input == Nil) {
        acc
      } else {
        val selected = input.head
        val limit = diskCapacity - selected
        val divided = input.tail.groupBy(_ <= limit)

        val (unavailableItems, availableItems) = (divided.get(false), divided.get(true).map(_.sorted.reverse.tail))
        val remains = unavailableItems.toList.flatten ::: availableItems.toList.flatten
        subroutine(remains, acc + 1)
      }
    }
    subroutine(input, 0)
  }

  def main(args: Array[String]) {
    val writer = new java.io.PrintWriter("small.out")
    try {
      process(io.Source.fromFile("A-small-practice (5).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, diskCapacity) = lineIn.next().split(" ").map(_.toInt)
      val fileSizes = lineIn.next().split(" ").map(_.toInt).toList

      lineOut(s"Case #$i: ${solve(fileSizes.sorted.reverse, diskCapacity)}")
    }
  }
}