LessMoneyMoreProblems.scala

object LessMoneyMoreProblems extends App {

  def countDenom(c: Long, coins: Seq[Int], target: Int): Int = {
    @annotation.tailrec
    def loop(n: Long, count: Int, unusedCoins: List[Int]): Int =
      if (n >= target) count
      else unusedCoins.headOption match {
        case Some(k) if k <= n + 1 =>
          loop(n + k * c, count, unusedCoins.tail)
        case _ =>
          loop(n + (n + 1) * c, count + 1, unusedCoins)
      }
    loop(0, 0, coins.sorted.toList)
  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      def ints() = lineIn.next() split ' ' map (_.toInt)
      val Array(c, d, v) = ints()
      lineOut(s"Case #$i: ${countDenom(c, ints(), v)}")
    }

  val filename = "C-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()
  }
}

LessMoneyMoreProblemsTest.scala

import org.scalatest._

import LessMoneyMoreProblems._

class LessMoneyMoreProblemsTest extends FunSuite {

  test("sample #1") {
    assert(countDenom(1, Seq(1, 2), 3) === 0)
  }

  test("sample #2") {
    assert(countDenom(1, Seq(1, 2, 5), 6) === 1)
  }

  test("sample #3") {
    assert(countDenom(2, Seq(3), 3) === 1)
  }

  test("sample #4") {
    assert(countDenom(1, Seq(1, 5, 10, 25, 50, 100), 100) === 3)
  }

  test("sample case") {
    val input = """4
1 2 3
1 2
1 3 6
1 2 5
2 1 3
3
1 6 100
1 5 10 25 50 100""".lines

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

    lineComparison(input, expected)
  }

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

    lineComparison(input, expected)
  }

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

}