← 返回题目列表

AtCoder · xmascon20_i

I. 实施我

中文机器翻译题面 查看原题

配点 : 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} 出 1 是 在 L 当数量以上时 0 和1 是 在 L 当数量以下时 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

G 是 您也可以写 0 和 按字典顺序比较 1 组成的长度 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) 是。