gNumbers.scala

package Main

import java.io.{FileOutputStream, FileInputStream}

import scala.io.StdIn

case class Balloon(x:Int, y:Int)
case class Node(time:Int, cost:Int)

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

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

    def solve(vj:Array[Int], balloons:List[Balloon], q:Int): Option[Int] = {
        def _solve(lastT:Int=Integer.MAX_VALUE, candidate:List[Array[Node]]):Int = {
            val filteredCandidate = candidate.map(nodes => nodes.filter(_.time < lastT))
            lazy val filteredCandidateMinByCost = filteredCandidate.map(_.minBy(_.cost))
            if (filteredCandidate.exists(_.isEmpty) || q < filteredCandidateMinByCost.map(_.cost).sum) {
                lastT
            } else {
                _solve(filteredCandidateMinByCost.map(_.time).max, filteredCandidate)
            }
        }

        val nodes = balloons.map((b:Balloon) => {
            vj.zipWithIndex.flatMap { case (v, idx) =>
                if (0 < v && 0 >= b.x) {
                    Some(Node((-b.x + v - 1) / v, Math.abs(b.y - idx)))
                } else if (0 > v && 0 <= b.x) {
                    Some(Node((b.x + (-v) - 1) / (-v), Math.abs(b.y - idx)))
                } else {
                    None
                }
            }
        })
        if (nodes.exists(_.isEmpty) || q < nodes.map(_.minBy(_.cost).cost).sum) {
            None
        } else {
            Some(_solve(candidate = nodes))
        }
    }

    val cases = StdIn.readLine().toInt
    (1 to cases) foreach { num =>
        val Array(n, m, q) = StdIn.readLine().split(" ").map(_.toInt)
        val vj = StdIn.readLine().split(" ").map(_.toInt)
        val balloons = for (i <- 0 until n) yield {
            val Array(x, y) = StdIn.readLine().split(" ").map(_.toInt)
            Balloon(x, y)
        }

        println(s"Case #$num: ${solve(vj, balloons.toList, q).map(_.toString).getOrElse("IMPOSSIBLE")}")
    }
}