LessMoney.scala

import java.io.FileOutputStream

import scala.io.Source

object LessMoney {
  val INPUT = "C-large-practice.in"
  val OUTPUT = INPUT.takeWhile(_ != '.') + ".out"
  val isConsole = false

  def numberOfDenominations(C: Long, D: List[Long], V: Long) = {
    def solve(n: Long, coins: List[Long], ans: Long): Long = coins match {
      case _ if n >= V => ans
      case x :: xs if x <= n + 1 => solve(n + (x * C), xs, ans)
      case _ => solve(n + ((n + 1) * C), coins, ans + 1)
    }
    solve(0, D, 0)
  }

  def main(args: Array[String]): Unit = {
    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 Array(c, _, v) = itr.next().split(' ').map(_.toLong)
          val denominations = itr.next().split(' ').map(_.toLong)
          println(f"Case #$set: ${numberOfDenominations(c, denominations.toList, v)}")
        }
      }
    } finally {
      stream.flush()
      if (!isConsole) stream.close()
    }
  }

}