RationalNumberTree.scala

case class RationalNumber(p: BigInt, q: BigInt) {
  override def toString() = {
    s"$p $q"
  }
}

object RationalNumberT {

  def getRationalNumber(n: BigInt): RationalNumber = {
    if (n == 1) RationalNumber(1, 1)
    else {
      val r = getRationalNumber(n >> 1)
      (n & 1).toInt match {
        case 0 => r.copy(q = r.p + r.q)
        case 1 => r.copy(p = r.p + r.q)
      }
    }
  }

  def getN(r: RationalNumber): BigInt = {
    if (r.p > r.q) {
      getN(r.copy(p = r.p - r.q)) << 1 | 1
    } else if (r.p < r.q) {
      getN(r.copy(q = r.q - r.p)) << 1
    } else {
      1
    }
  }

  def process(iter: Iterator[String])(pr: String => Unit) {
    for (i <- 1 to iter.next().toInt) yield {
      val line = iter.next().split(' ')
      val value = line.tail.map(BigInt(_))
      pr(s"Case #$i: ${if (line.head.toInt == 1) getRationalNumber(value.head) else getN(RationalNumber(value(0), value(1))).toString}")
    }
  }

  def main(args: Array[String]) {
    val in = Source.fromFile(new File("B-large-practice.in"))
    val out = new PrintStream(new File("test.out"))
    try {
      process(in.getLines) { s: String => println(s) }
    } finally {
      out.flush; out.close
    }
  }
}