Slides.scala

object Slides extends App {

  def linkMatrix(b: Int, m: Long): Option[String] = {
    val max = BigInt(2).pow(b-2)

    val last: Option[Int] = (max - m).toLong match {
      case 0L => Some(1)
      case x if x > 0 => Some(0)
      case _ => None
    }

    last.map{ n =>
      ("0"*b ++ (m-n).toBinaryString).takeRight(b-1) ++ n.toString ++ "\n" ++
      Seq.tabulate(b-1){ i => "0" * (i + 2) ++ "1" * (b - i - 2) }.mkString("\n")
    }
  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      val Array(b, m) = lineIn.next() split " "
      lineOut(s"Case #$i: ${linkMatrix(b.toInt, m.toLong).map("POSSIBLE\n" ++ _) getOrElse "IMPOSSIBLE"}")
    }

  val filename = "B-large-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()
  }
}

SlidesTest.scala

import org.scalatest._

import Slides._

class SlidesTest extends FunSuite with Matchers {

  test("sample #1") {
    assert(linkMatrix(5, 4) === Some("""01000
00111
00011
00001
00000"""))
  }

  test("sample #2") {
    assert(linkMatrix(2, 1) === Some("""01
00"""))
  }

  test("sample #3") {
    assert(linkMatrix(4, 20) === None)
  }

  test("b=5, m=8") {
    assert(linkMatrix(5, 8) === Some("""01111
00111
00011
00001
00000"""))
  }

  test("sample case") {
    val input = """3
5 4
2 1
4 20""".lines

    val expected = """Case #1: POSSIBLE
01000
00111
00011
00001
00000
Case #2: POSSIBLE
01
00
Case #3: IMPOSSIBLE""".lines

    lineComparison(input, expected)
  }

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

    lineComparison(input, expected)
  }

  test("full large case") {
    val input = io.Source.fromFile("B-large-practice.in").getLines()
    val expected = io.Source.fromFile("B-large-practice.out").getLines()

    lineComparison(input, expected)
  }

  def lineComparison(input: Iterator[String], expected: Iterator[String]): Unit = {
    process(input) { s =>
      for (line <- s.lines) assert(line.trim === expected.next().trim)
    }
    assert(expected.hasNext === false, "Finished too fast.")
  }

}