PickingUpChicks.scala

object PickingUpChicks extends App {

  def minSwap(k: Int, b: Int, t: Int, xs: Seq[Int], vs: Seq[Int]): Option[Int] = {

    @annotation.tailrec
    def loop(chicks: List[(Int, Int)], hopeless: Int, k: Int, count: Int): Option[Int] = chicks match {
      case _ if k == 0 => Some(count)
      case Nil         => None
      case (x, v) :: tail =>
        val (dh, dk, dc) = if (x + v * t >= b) (0, -1, hopeless) else (1, 0, 0)
        loop(tail, hopeless + dh, k + dk, count + dc)
    }

    loop((xs zip vs).sortBy(-_._1).toList, 0, k, 0)
  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      def readInts() = lineIn.next().split(' ').map(_.toInt)
      val Array(n, k, b, t) = readInts()
      lineOut(s"Case #$i: ${minSwap(k, b, t, readInts(), readInts()) getOrElse "IMPOSSIBLE"}")
    }

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

}

PickingUpChicksTest.scala

import org.scalatest._

import PickingUpChicks._

class PickingUpChicksTest extends FunSuite {

  test("sample #1") {
    assert(minSwap(3, 10, 5, Seq(0, 2, 5, 6, 7), Seq(1, 1, 1, 1, 4)) === Some(0))
  }

  test("sample #2") {
    assert(minSwap(3, 10, 5, Seq(0, 2, 3, 5, 7), Seq(2, 1, 1, 1, 4)) === Some(2))
  }

  test("sample #3") {
    assert(minSwap(3, 10, 5, Seq(0, 2, 3, 4, 7), Seq(2, 1, 1, 1, 4)) === None)
  }
  
  test("sample case") {
    val input = """3
5 3 10 5
0 2 5 6 7
1 1 1 1 4
5 3 10 5
0 2 3 5 7
2 1 1 1 4
5 3 10 5
0 2 3 4 7
2 1 1 1 4""".lines

    val expected = """Case #1: 0
Case #2: 2
Case #3: IMPOSSIBLE""".lines

    lineComparison(input, expected)
  }

  test("full small case") {
    val input = io.Source.fromFile("B-small-practice.in").getLines()
    val expected = io.Source.fromFile("B-small-practice.out").getLines()

    lineComparison(input, expected)
  }

  test("full large case") {
    val input = io.Source.fromFile("B-large-practice.in").getLines()
    val expected = io.Source.fromFile("B-large-practice.out").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.")
  }

}