I - Implement Me Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100

くろうさ「任意のブール関数は甘え」

しろうさ「」

くろうさ「というのはひどいから 1 種類だけ許してあげる」

しろうさ「1 種類だけで論理回路みたいなの組むってことですか?」

くろうさ「1 種類だけで論理回路みたいなの組んでください」

しろうさ「これ無理じゃない?」

くろうさ「今年は無理かどうかの判定もがんばってねっ」

問題文

正の整数 M, L が与えられる.M 変数ブール関数 F\colon \{0, 1\}^M \to \{0, 1\} を次のように定める:F(x_0, \ldots, x_{M-1})x_0, \ldots, x_{M-1} のうち 1L 個以上であるとき 0 であり,1L 個未満であるとき 1 である

また,正の整数 N および N 変数ブール関数 G\colon \{0, 1\}^N \to \{0, 1\} が与えられる.F だけを使って,G を実現する以下の仕様を満たすプログラムを 1 つ求めよ.そのようなプログラムが存在しない場合はそれを指摘せよ.

プログラムは 10^4 個のブール変数 a[0], \ldots, a[10^4-1] を扱うことができる.プログラムは 0 個以上 10^4 個以下の命令からなり,それらが順に実行される.各命令は添え字 j, i_0, \ldots, i_{M-1} によって表され,F(a[i_0], \ldots, a[i_{M-1}]) を計算し,その結果を a[j] に代入することを意味する.

任意の (y_0, \ldots, y_{N-1}) \in \{0, 1\}^N に対し,プログラムの実行開始時に a[0], \ldots, a[N-1] の値が入力 y_0, \ldots, y_{N-1} であり他の変数が初期化されていない場合,実行終了時に a[N] の値が G(y_0, \ldots, y_{N-1}) でなければならない.また,実行の途中で初期化も代入もされていない変数を F の引数に渡してはならない.

簡易的な出力チェッカーがここから利用可能である.

制約

  • 1 \le M \le 8
  • 1 \le L \le M
  • 1 \le N \le 8

部分点

  • N \le 2 を満たすデータセットに正解した場合は,10 点が与えられる.
  • 追加制約のないデータセットに正解した場合は,上記とは別に 90 点が与えられる.

入力

入力は以下の形式で標準入力から与えられる.

M
L
N
G

G01 からなる長さ 2^N の文字列として表される.各 (y_0, \ldots, y_{N-1}) \in \{0, 1\}^N に対し,\left(1 + \sum_{k=0}^{N-1} 2^k y_k\right) 文字目は G(y_0, \ldots, y_{N-1}) の値を表す.

出力

条件を満たすプログラムが存在しない場合は,-1 と出力せよ.

条件を満たすプログラムが存在する場合は,そのうち 1 つを次の形式で出力せよ:1 行目に命令の個数 p を出力し,続く p 行に実行する順に命令を出力する.各命令はそれを表す添え字 j, i_0, \ldots, i_{M-1} をこの順に空白区切りで出力する.

簡易的な出力チェッカーがここから利用可能である.


入力例 1

2
1
3
00000101

出力例 1

3
2020 0 0
1224 2 2
3 2020 1224

この例では,F(x_0, x_1) = (x_0 \operatorname{NOR} x_1)G(y_0, y_1, y_2) = (y_0 \operatorname{AND} y_2) である.