AT_xmascon20_i.Implement Me

给定两个正整数 $M$ 和 $L$。定义一个 $M$ 变量的布尔函数 $F\colon \{0, 1\}^M \to \{0, 1\}$，其规则为：如果 $x_0, \ldots, x_{M-1}$ 中的值中有至少 $L$ 个为 $1$，那么 $F(x_0, \ldots, x_{M-1}) = 0$；否则，其结果为 $1$。

此外，还有一个正整数 $N$ 以及一个 $N$ 变量的布尔函数 $G\colon \{0, 1\}^N \to \{0, 1\}$。你的任务是只使用函数 $F$ 来实现 $G$，并满足以下条件。如果无法完成这样的实现，请指出。

程序最多可以处理 $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$ 的参数。

这里提供了一个简单的输出检查器。

输入通过标准输入给出，格式如下：

$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。

若可以实现，输出一个满足条件的程序。首行输出指令数量 $p$，接下来的 $p$ 行分别输出每条指令。每条指令用空格分隔的格式输出：$j, i_0, \ldots, i_{M-1}$。

这里提供了一个简单的输出检查器。

约束

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

部分得分

• 在符合 $N \le 2$ 的数据集上正确解答，将获得 10 分。
• 满足其他条件的数据集上正确解答，将额外获得 90 分。

示例解释 1

在这个例子中，$F(x_0, x_1) = (x_0 \operatorname{NOR} x_1)$，$G(y_0, y_1, y_2) = (y_0 \operatorname{AND} y_2)$。

本翻译由 AI 自动生成