LessMoneyMoreProblems.scala

package Main

import java.io.{FileOutputStream, FileInputStream}

import scala.annotation.tailrec
import scala.io.StdIn


object Main extends App {
    Console.setIn(new FileInputStream("example.in"))

    Console.setIn(new FileInputStream("C-large-practice.in"))
    Console.setOut(new FileOutputStream("C-large-practice.out"))


    def solve(c: Int, target: Int, coins: List[Int]): Int = {
        @tailrec
        def _solve(n: Long, remainCoins: List[Int], ans: Int): Int = {
            if (n >= target) ans
            else if (remainCoins.nonEmpty && n + 1 >= remainCoins.head)
                _solve(n + remainCoins.head.toLong * c, remainCoins.tail, ans)
            else _solve(n + (n + 1) * c, remainCoins, ans + 1)
        }
        _solve(0, coins.sorted, 0)
    }

    val cases = StdIn.readLine().toInt
    (1 to cases) foreach { n =>
        val Array(c, _, v) = StdIn.readLine().split(" ").map(_.toInt)
        val coins = StdIn.readLine().split(" ").toList.map(_.toInt)

        println(s"Case #$n: ${solve(c, v, coins)}")
    }
}