Telephone Network (UVa Live Archive Europe Northwestern 2010)
問題
図の様な入力と出力が2^n個あるスイッチ式の変換器で電話網を繋げる。m個の条件を満たすような変換の仕方をした時に、各クエリの入力が上から何番目の中央のスイッチを通るか答えよ。
1<=n<=16
1<=m<=2^n
解法
(たぶん)S(j)の変換器は任意の置換を表現できる。なのでS(j)の一番外側のスイッチの割り当てを被らないように2SATで求めれば良い。S(j)のスイッチの入れ方が決まったらS(j-1)のスイッチを再帰的に求める。
