class Chomps(N: Int) {
  require(N > 0 && N.toLong * N.toLong <= Int.MaxValue.toLong)
  private val row = Array.fill(N)(N)
  private var remaining = N * N

  def Count(): Int = remaining

  def Legal(x: Int, y: Int): Boolean =
    0 <= x && x < N && 0 <= y && y < N && x < row(y)

  def Move(x: Int, y: Int): Unit = {
    require(Legal(x, y))
    var j = y
    while (j < N) {
      val next = math.min(row(j), x)
      remaining -= row(j) - next
      row(j) = next
      j += 1
    }
  }

  def Display(): Unit = {
    require(N < 10)
    var y = N - 1
    while (y >= 0) {
      print(y.toString + " ")
      var x = 0
      while (x < N) {
        print(if (x < row(y)) "* " else "  ")
        x += 1
      }
      println()
      y -= 1
    }
    print("  ")
    var x = 0
    while (x < N) {
      print(x.toString + " ")
      x += 1
    }
    println()
  }
}

def preorderIterative(t: Tree): Unit = {
  val pending = new Stack
  if (t != null) pending.push(t)
  while (!pending.isEmpty) {
    val u = pending.pop
    println(u.datum)
    if (u.right != null) pending.push(u.right)
    if (u.left != null) pending.push(u.left)
  }
}

class Stack {
  private val MAX = 1000
  private val data = new Array[Tree](MAX)
  private var used = 0

  // Pre: used < MAX.
  def push(t: Tree): Unit = {
    require(used < MAX, "Stack full")
    data(used) = t
    used += 1
  }

  // Pre: used > 0.
  def pop: Tree = {
    require(used > 0, "Stack empty")
    used -= 1
    val result = data(used)
    data(used) = null
    result
  }

  // Pre: true.
  def isEmpty: Boolean = used == 0
}

def preorderRecursive(t: Tree): Unit = {
  if (t != null) {
    println(t.datum)
    preorderRecursive(t.left)
    preorderRecursive(t.right)
  }
}

def recall(name: String): String = {
  require(name != null)
  val p = findPrev(name)
  require(p.next != null, "Name is not in the book")
  val found = p.next
  if (p ne header) {
    p.next = found.next
    found.next = header.next
    header.next = found
  }
  found.number
}

class LinkedBook extends Book {
  private val header = new Node("", "", null)

  // Pre: name != null.
  // Post: result is header or a real node.
  // All real nodes through result have names different from name.
  // result.next is null or has name equal to name.
  // No state is changed.
  private def findPrev(name: String): Node = {
    require(name != null)
    var p = header
    while (p.next != null && p.next.name != name) {
      p = p.next
    }
    p
  }

  def store(name: String, number: String): Unit = {
    require(name != null && number != null)
    val p = findPrev(name)
    if (p.next == null)
      p.next = new Node(name, number, null)
    else
      p.next.number = number
  }

  def recall(name: String): String = {
    require(name != null)
    val p = findPrev(name)
    require(p.next != null, "Name is not in the book")
    p.next.number
  }

  def isInBook(name: String): Boolean = {
    require(name != null)
    findPrev(name).next != null
  }

  def delete(name: String): Boolean = {
    require(name != null)
    val p = findPrev(name)
    if (p.next == null) false
    else {
      p.next = p.next.next
      true
    }
  }
}

class Node(var name: String, var number: String, var next: Node)

trait Book {
  // Abstract state B: finite partial map String -> String; initially empty.

  // Pre: name != null && number != null.
  // Post: B' = B updated at name with number.
  def store(name: String, number: String): Unit

  // Pre: name != null && name is in dom(B).
  // Post: result = B(name), and B' = B.
  def recall(name: String): String

  // Pre: name != null.
  // Post: result iff name is in dom(B), and B' = B.
  def isInBook(name: String): Boolean

  // Pre: name != null.
  // Post: result iff name was in dom(B); B' = B with name removed.
  def delete(name: String): Boolean
}

def missing(): Int = {
  val n = a.length
  var lo = 0L
  var hi = n.toLong + 1L
  var l = 0
  var r = n
  while (hi - lo > 1L) {
    val p = lo + (hi - lo) / 2L
    val k = partition(l, r, p.toInt)
    if ((k - l).toLong < p - lo) {
      hi = p
      r = k
    } else {
      lo = p
      l = k
    }
  }
  lo.toInt
}

def partition(l: Int, r: Int, p: Int): Int = {
  require(0 <= l && l <= r && r <= a.length)
  var k = l
  var j = l
  while (j < r) {
    if (a(j) < p) {
      val t = a(k)
      a(k) = a(j)
      a(j) = t
      k += 1
    }
    j += 1
  }
  k
}

def printRat(num: Int, den: Int): Unit = {
  print(num.toString + "/" + den.toString)
}

def printEgypt(e: Array[Int]): Unit = {
  if (e.isEmpty) print("0")
  var i = 0
  while (i < e.length) {
    if (i > 0) print(" + ")
    print("1/" + e(i).toString)
    i += 1
  }
}

def toRatExact(e: Array[Int]): (BigInt, BigInt) = {
  var n = BigInt(0)
  var d = BigInt(1)
  var i = 0
  while (i < e.length) {
    require(e(i) > 0)
    val x = BigInt(e(i))
    val g = d.gcd(x)
    val nextN = n * (x / g) + d / g
    val nextD = d * (x / g)
    val h = nextN.gcd(nextD)
    n = nextN / h
    d = nextD / h
    i += 1
  }
  (n, d)
}

def toRat(e: Array[Int]): (Int, Int) = {
  val result = toRatExact(e)
  require(result._1.isValidInt && result._2.isValidInt,
          "Reduced result does not fit (Int, Int)")
  (result._1.toInt, result._2.toInt)
}

def fromRat(num: Int, den: Int): Array[Int] = {
  require(0 <= num && num < den)
  val start = Reduce(num, den)
  var n = BigInt(start._1)
  var d = BigInt(start._2)
  var e = Array.empty[Int]
  while (n > 0) {
    val q = (d + n - 1) / n
    if (!q.isValidInt) return Array.fill(num)(den)
    e = e :+ q.toInt
    val nextN = n * q - d
    val nextD = d * q
    val g = nextN.gcd(nextD)
    n = nextN / g
    d = nextD / g
  }
  e
}