NewLotteryGame.scala

import scala.io.Source
import java.io.PrintWriter
import java.io.File

object NewLotteryGame {

  implicit class IntWrapper(n: Int) {
    def toBit: List[Int] = (n - 1).toBinaryString.reverse.padTo(32, "0").map(_.toString.toInt).toList
  }

  implicit def numberToBit(n: Int) = n.toBit // number => Bits

  case class Key(a: List[Int], b: List[Int], k: List[Int], pos: Int)

  var memo: Map[Key, Long] = Map();

  def solve(a: List[Int], b: List[Int], k: List[Int], idx: Int): Long = {
    val key = Key(a, b, k, idx)

    if (idx < 0) 1
    else if (memo.contains(key)) memo(key)
    else {
      var sum = 0L
      for {
        aa <- 0 to a(idx) // 0 or 1
        bb <- 0 to b(idx) // 0 or 1
        if ((aa & bb) <= k(idx))
      } {
        val filled = List.fill(32)(1)
        val newA = if (aa == a(idx)) a else filled
        val newB = if (bb == b(idx)) b else filled
        val newK = if ((aa & bb) == k(idx)) k else filled
        sum += solve(newA, newB, newK, idx - 1)
        memo += (key -> sum)
      }
      sum
    }
  }

  def main(args: Array[String]) {
    val lines = Source.fromFile("B-large-practice.in").getLines();
    val printer = new PrintWriter(new File("B-large.out"));

    (1 to lines.next.toInt).foreach { i =>
      val Array(a, b, k) = lines.next.split(" ").map(_.toInt)
      printer.println(s"Case #$i: " + solve(a, b, k, 32 - 1));
    }
    printer.flush
  }
}