Google Code Jam 2014 Qualification Round B Cookie Clicker Alpha

cookie_clicker_alpha.scala

import scala.collection.mutable.Map 

object cookie_clicker_alpha extends App {
    def solve(C: Double, F: Double, X: Double): Double = {
        val cache: Map[Int, Double] = Map()

        def farm_time(num_farm: Int): Double = {
            /*
            g(0) = 0
            g(1) = C / 2
            g(2) = g(1) + C / (2 + 1 * F)
            g(3) = g(2) + C / (2 + 2 * F)
            g(4) = g(3) + C / (2 + 3 * F)
            ...
            g(n) = g(n-1) + C / (2 + (n-1) * F)
            */
            if (num_farm == 0) 0
            else if (num_farm == 1) C / 2
            else {
                if (cache.contains(num_farm)) cache(num_farm)
                else {
                	val time = farm_time(num_farm - 1) + C / (2 + (num_farm - 1) * F)
                	cache(num_farm) = time
                	time
                }
            }
        }

        def total_time(num_farm: Int): Double = {
            /*
            f(0) = X / 2
            f(1) = X / (2 + 1 * F) + g(1)
            f(2) = X / (2 + 2 * F) + g(2)
            f(3) = X / (2 + 3 * F) + g(3)
            ...
            f(n) = X / (2 + n * F) + g(n)
            */
            if (num_farm == 0) X / 2
            else X / (2 + num_farm * F) + farm_time(num_farm)
        }

        val max_num_farm = (X / C).toInt
        val times = for (num_farm <- 0 to max_num_farm) yield total_time(num_farm)
        times.min
    }

    //////////
    // main //
    //////////
    if (args.length > 0) Console.setIn(new java.io.FileInputStream(args(0)))
    if (args.length > 1) Console.setOut(new java.io.FileOutputStream(args(1)))

    for (t <- 1 to readInt) {
    	val dbls = readLine.split(" ").map(_.toDouble).iterator
    	val C = dbls.next
    	val F = dbls.next
    	val X = dbls.next
        println("Case #%d: %.7f".format(t, solve(C, F, X)))
    }
}