SwingingWild.scala

object SwingingWild extends App {

  def possibleToReach(vines: IndexedSeq[(Int, Int)], distance: Int): Boolean = {

    def reach(i: Int, h: Int) = vines(i)._1 + h

    @annotation.tailrec
    def loop(vine: Int, h: Int): Boolean = 
      if (vines(vine)._1 + h >= distance) true
      else {
        val nexts = for {
          i <- vine + 1 until vines.size if vines(i)._1 <= reach(vine, h)
          nextHeight = (vines(i)._1 - vines(vine)._1) min vines(i)._2
          nextReach = reach(i, nextHeight) if nextReach > reach(vine, h)
        } yield (i, nextHeight, nextReach)
        if (nexts.isEmpty) false
        else {
          val (nextVine, nextHeight, nextReach) = nexts.maxBy(_._3)
          loop(nextVine, nextHeight)
        }
      }
    
    loop(0, vines(0)._1)
  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      val n = lineIn.next().toInt
      val vines = IndexedSeq.fill(n) {
        val Array(d, i) = lineIn.next().split(' ').map(_.toInt)
        (d, i)
      }
      val d = lineIn.next().toInt
      lineOut(s"Case #$i: ${if (possibleToReach(vines, d)) "YES" else "NO"}")
    }

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

}

SwingingWildTest.scala

import org.scalatest._

import SwingingWild._

class SwingingWildTest extends FunSuite {
  
  test("sample #1") {
    assert(possibleToReach(Vector((3,4), (4,10), (6, 10)), 9) === true)
  }
  
  test("sample #2") {
    assert(possibleToReach(Vector((3,4), (4,10), (7, 10)), 9) === false)
  }
  
  test("sample #3") {
    assert(possibleToReach(Vector((6,6), (10,3)), 13) === true)
  }
  
  test("sample #4") {
    assert(possibleToReach(Vector((6,6), (10,3)), 14) === false)
  }
  
  test("sample case") {
    val input = """4
3
3 4
4 10
6 10
9
3
3 4
4 10
7 10
9
2
6 6
10 3
13
2
6 6
10 3
14""".lines

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

    lineComparison(input, expected)
  }

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

    lineComparison(input, expected)
  }

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

}