RationalNumberTree.scala

object RationalNumberTree extends App {

  def position(p: BigInt, q: BigInt): BigInt = {

    @annotation.tailrec
    def getForks(p: BigInt, q: BigInt, acc: List[Boolean] = Nil): List[Boolean] =
      if (p == q) acc
      else {
        val (p0, q0, acc0) = if (p < q) (p, q - p, false :: acc) else (p - q, q, true :: acc)
        getForks(p0, q0, acc0)
      }
    
    def to(r: List[Boolean]): BigInt =
      if (r.isEmpty) 0
      else (if (r.head) 1 else 0) + to(r.tail) * 2

    val forks = getForks(p, q)

    (BigInt(2) pow forks.size) + to(forks.reverse)

  }

  def find(n: BigInt): (BigInt, BigInt) = {

    def to(s: List[Char], p: BigInt = 1, q: BigInt = 1): (BigInt, BigInt) = s match {
      case Nil => (p, q)
      case x :: xs =>
        if (x == '0') to(xs, p, p + q) else to(xs, p + q, q)
    }

    to((n toString 2).tail.toList)
  }

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

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

}