RationalNumberTree.scala

object RationalNumberTree extends App {

  private lazy val One = BigInt(1)
  private lazy val Two = BigInt(2)

  @annotation.tailrec
  def position(p: BigInt, q: BigInt, acc: List[Int] = Nil): BigInt = {
    if (p == q) (One /: acc)(2 * _ + _)
    else {
      val (p0, q0, k) = if (p < q) (p, q - p, 0) else (p - q, q, 1)
      position(p0, q0, k :: acc)
    }
  }

  def find(n: BigInt): Seq[BigInt] = (Seq(One, One) /: (n toString 2).tail.toSeq) {
    case (Seq(p, q), '0') => Seq(p, p + q)
    case (Seq(p, q), '1') => Seq(p + q, q)
  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) lineOut(s"Case #$i: ${
      lineIn.next() split ' ' map BigInt.apply match {
        case Array(One, n) => find(n) mkString " "
        case Array(Two, p, q) => position(p, q)
      }
    }")

  val writer = new java.io.PrintWriter("b.out")
  try {
    process(io.Source.fromFile("B-large-practice.in").getLines)(writer.println)
  } finally {
    writer.flush(); writer.close()
  }

}