配点: 100 点
問題文
N 个开关,每个开关有一个 它的编号为 1, 2, 3, ..., N 。每个开关都有两种状态,0 或 1。
现在,您有号码 添加了 N+1, N+2, ..., N+M 您可以使用 M 存储器创建电路。 (M 的值可以自由确定。 )
内存包含以下内容 4 有不同的类型。下面的解释中,对应的内存编号为 x 。
① 与内存
它由两个开关/存储器连接,并且它们已编号。
比方说 u, v (u < x, v < x) 。数量 x 的内存值为数字
标有 u 的开关/存储器值/编号
如果 v 的开关/存储器的值都是1,则为1,否则为0。
② 或内存
如果
它由两个开关/存储器连接,并且它们已编号。
比方说 u, v (u < x, v < x) 。数量 x 的内存值为数字
标有 u 的开关/存储器值/编号
如果 v 的开关/存储器值之一为 1,则该值为 1,否则为 0。
③ 异或存储器
如果
它由两个开关/存储器连接,并且它们已编号。
比方说 u, v (u < x, v < x) 。数量 x 的内存值为数字
标有 u 的开关/存储器值/编号
如果 v 的开关/存储器值只有一个为1,则为1,否则为0。
④ 不记忆
它由一个开关/存储器连接,并且已编号。
如果 u (u < x) 。数量 x 的内存值为数字
标有 u 的开关/存储器的值为0,则为1,否则为0。
例如,考虑如下所示的电路。

在该电路中,每个开关状态下每个存储器的状态如下表所示。
| 开关 1 | 开关 2 | 开关 3 | 内存 4 | 内存 5 | 内存 6 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 |
因此,{开关1,开关2,开关3}的状态为{0, 1, 0}, {1, 0, 0} 内存6的值可以是 1 变为。
对此,请解决以下两个问题。
当T=1时
开关状态为 2^N 方法有很多,但只是 K 关于街道、号码 N+M 内存(M=0 如果开关)值为
请构造一个电路,使得 1 。
请勿使用超过
但是,2^{N}×4N 的内存。
当 T = 2 时
开关状态为
该数字当且仅当 S_1, S_2, S_3, ..., S_K 当且仅当数字 N+M 内存(M=0 如果开关)值为
请构造一个电路,使得 1 。
请勿使用超过
但是,50 \ 000 的内存。
制約
- 1 \leq T \leq 2
- 2 \leq N \leq 10
- 1 \leq K \leq 2^{N}-1
- T, N, K 是一个整数 由
小作业/分数
对于这个问题,2 有两个子作业。
- (30 点) T = 1.
- (70 点) T = 2.
在子任务 1 中,每个测试用例的分数确定如下。该子任务中所有测试用例的最低分数将是该子任务的分数。 当
- 2^{N}×4N < M 时,0 点.
- 2^{N}×2 < M \leq 2^{N}×4N 时,10 点.
- N^2 < M \leq 2^{N}×2 时,16 点.
- N-1 < M \leq N^2 时,23 点.
- M \leq N-1 时,30 点満点.
接下来,在子任务 2 中, M 的最大值 L_2 ,该子任务的分数如下。
- 50 \ 001 \leq L_2 时,0 点.
- 4 \ 201 \leq L_2 \leq 50 \ 000 时,15 点.
- 3 \ 101 \leq L_2 \leq 4 \ 200 时,18 点.
- 2 \ 101 \leq L_2 \leq 3 \ 100 时,21 点.
- 1 \ 601 \leq L_2 \leq 2 \ 100 时,25 点.
- 1 \ 201 \leq L_2 \leq 1 \ 600 时,29 点.
- 751 \leq L_2 \leq 1 \ 200 时,35 点.
- 501 \leq L_2 \leq 750 时,floor(70 - \frac{L_2 - 500}{8}) 点.
- L_2 \leq 500 时,70 点満点.
入力
输入是按以下格式从标准输入给出的。
(☆) T = 1 什么时候
1 N K
但是,N 是开关数量,K 是号码 N+M 开关 (M=0 表示存储器的值应为1的状态数。
(★) T = 2 什么时候
2 N K S_1 S_2 S_3 : S_K
在这里,S_i 是号码 N+M 开关 (
在M=0 的情况下,内存)的值应该是1,
这是i 第一篇。
S_i 表示 N 用一串字符表示,i 第一个字母是
如果 0 第 i 个开关的状态为0,i 第一个字母是
如果 1 第 i 表示开关状态为1。
例如,N = 4 把 S_i = 0101 ,开关 2, 4 为 1,开关
它代表 1, 3 为0的状态。
出力
请输出如下所示的逻辑电路的配置方法。 请输出
M (番号 N+1 のメモリの情報) (番号 N+2 のメモリの情報) (番号 N+3 のメモリの情報) : (番号 N+M のメモリの情報)
番号 x 的内存信息如下。
和内存
AND u v
这是号码 来自 u 和 v 的开关/存储器,编号 表示连接到 x 的内存。 必须满足u < x, v < x 。 (但是 u = v 没问题)
对于 OR 存储器
OR u v
这是号码 来自 u 和 v 的开关/存储器,编号 表示连接到 x 的内存。 必须满足u < x, v < x 。 (但是 u = v 没问题)
对于 XOR 内存
XOR u v
这是号码 来自 u 和 v 的开关/存储器,编号 表示连接到 x 的内存。 必须满足u < x, v < x 。 (但是 u = v 没问题)
对于 NOT 内存 必须满足
NOT u
这是号码 来自 u 的开关/存储器,编号 表示连接到 x 的内存。 必须满足u < x 。
入力例 1
1 3 2
出力例 1
3 XOR 1 2 NOT 3 AND 4 5
对于此输出, 对于N = 2 反对 M = 3 和N 以上 N^2 因为它小于 23 点。
入力例 2
2 3 2 010 100
出力例 2
3 XOR 1 2 NOT 3 AND 4 5
入力例 3
1 5 24
出力例 3
1 OR 1 2
入力例 4
2 3 4 001 101 011 111
出力例 4
0