Osmos.scala

import scala.io.Source
import scala.math.min
import java.io.FileOutputStream
import java.io.File
import java.io.PrintWriter

object Osmos {

  val in = Source.fromFile("large.in").getLines;
  val out = new PrintWriter(new File("large.out"));

  case class TestCase(curMoteSize: Int, motes: List[Int], wildCardCount: Int = 0) {

    def smallestMote = motes(0)
    
    def minCount(mc:Int) = min(mc, wildCardCount + motes.size)

    def solve(preMc:Int = motes.size): Int = {
      val mc = minCount(preMc)
      if (1 == curMoteSize || motes.isEmpty) {
        mc
      } else if (curMoteSize > smallestMote) {
        new TestCase(curMoteSize + smallestMote, motes.tail, wildCardCount).solve(mc)
      } else {
        new TestCase(curMoteSize * 2 - 1, motes, wildCardCount + 1).solve(mc)
      }
    }
  }

  def main(args: Array[String]) {
    val nOfCases = in.next.toInt

    val testCases = for {
      i <- 1 to nOfCases
      val Array(init, _) = in.next.split(" ").map(_.toInt)
      val moteList = in.next.split(" ").map(_.toInt).toList
      val res = TestCase(init, moteList.sorted).solve()
    } {
      out.println(s"Case #$i: $res")
      println(s"Case #$i: $res")
    }
    out.flush()
  }
}