olimpiadka

package prost

import scala.collection._

object Main extends App {
  val n = 1000
  val b = Set("111", "101")
  val r = 2

  def arrangements(length: Int) = {

    def arrangements(acc: List[Char]): List[List[Char]] = {
      if (acc.size == length)
        List(acc.reverse)
      else
        arrangements('0' :: acc) ::: arrangements('1' :: acc)
    }

    arrangements(Nil).map(_.mkString)
  }

  val endings = arrangements(r)

  def p(sequence: String) =
    if (b.contains(sequence)) 0 else 1

  val qNextFunc = endings.map(ending =>
    ending -> ((q: Map[String, BigInt]) =>
        q('0' + ending.dropRight(1)) * p('0' + ending) +
        q('1' + ending.dropRight(1)) * p('1' + ending)
  )).toMap

  def qNext(q: Map[String, BigInt]) =
    q.map(kv => kv._1 -> qNextFunc(kv._1)(q)).toMap

  val q = endings.map(_ -> BigInt(1)).toMap
  println(Stream.iterate(q)(qNext)(n - r).values.sum)
}