← 返回题目列表

AtCoder · gigacode_2019_h

H. 逻辑电路配置

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

配点: 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 有两个子作业。

  1. (30 点) T = 1.
  2. (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