分数: 466 分
问题陈述
Takahashi 正在尝试通过发送密码来进行身份验证 N 代理。
密码是一个长度序列 L 由之间的整数组成 1 和 K 包括: S = (S_1, S_2, \dots, S_L).
高桥有一份褪色的备忘录,可以将其解读为长度序列 L: B = (B_1, B_2, \dots, B_L)。在这里,
- If B_j = 0,表示无法读取该位置的值,并且 S_j 可以设置为之间的任何整数 1 和 K 包括在内。
- If B_j \neq 0,那么 S_j = B_j 必须保留。
在开始传输之前,高桥填写所有未确定的位置以完成密码 S。每个位置可以独立地分配之间的任何整数 1 和 K 包括在内(不同位置可以使用相同的值)。一旦完成, S 此后无法更改。
对于传输,使用单个密码设备。该设备拥有一个 转换规则 作为排列 C = (C_1, C_2, \dots, C_K) on \{1, 2, \dots, K\}。最初, C 是恒等排列,即 C_x = x 对于所有人 x (1 \leq x \leq K).
完成密码后,高桥将其发送给所有人 N 每个代理只执行一次,按照他选择的顺序。传送给代理时 i,按此顺序执行以下操作:
- 传输和身份验证检查:使用设备当前的转换规则 C,密码的每个元素 S 已加密并发送。具体来说,代理收到的序列 i is (C_{S_1}, C_{S_2}, \dots, C_{S_L})。如果这个序列与代理完全匹配 i的验证码 T_i = (T_{i,1}, T_{i,2}, \dots, T_{i,L}),然后代理 i的身份验证成功。
- 转换规则更新:无论认证是否成功,都会使用agent更新设备的转换规则 i的排列 A_i = (A_{i,1}, A_{i,2}, \dots, A_{i,K})。新的转换规则 C' 为所有定义 x (1 \leq x \leq K)由
C'_x = A_{i, C_x}
(即,它被替换为组合物 A_i \circ C).
高桥可以自由选择如何填写密码 S 以及传输到的顺序 N 代理。
找出当两个选择都最佳时,身份验证可以成功的最大代理数量。此外,在所有已完成的密码中 S 达到这个最大值,找到字典顺序最小的一个。这里,“达到最大值”是指存在某种传输顺序,在该传输顺序下认证成功的代理的数量等于最大值。
对于两个序列 U 和 V 长度 L,如果 U \neq V,让 j 是它们不同的第一个位置;那么 U 按字典顺序小于 V if U_j < V_j.
约束
- 1 \leq N \leq 8
- 1 \leq K \leq 8
- 1 \leq L \leq 200
- 0 \leq B_j \leq K (1 \leq j \leq L)
- 1 \leq T_{i,j} \leq K (1 \leq i \leq N, 1 \leq j \leq L)
- 1 \leq A_{i,k} \leq K (1 \leq i \leq N, 1 \leq k \leq K)
- A_i 是一个排列 \{1, 2, \dots, K\} (包含来自的每个整数 1 to K 恰好一次)
- 所有输入值均为整数
输入
输入是按以下格式从标准输入给出的。
N K L
B_1 B_2 \dots B_L
T_{1,1} T_{1,2} \dots T_{1,L}
A_{1,1} A_{1,2} \dots A_{1,K}
T_{2,1} T_{2,2} \dots T_{2,L}
A_{2,1} A_{2,2} \dots A_{2,K}
\vdots
T_{N,1} T_{N,2} \dots T_{N,L}
A_{N,1} A_{N,2} \dots A_{N,K}
- 第一行包含代理数量 N,值类型的数量 K,以及密码长度 L,用空格分隔。
- 第二行包含序列 B 代表褪色的备忘录,以空格分隔。
- 对于每个 i (1 \leq i \leq N),以下两行提供有关代理的信息 i:
- 线 2i + 1 包含代理 i的验证码 T_i,用空格分隔。
- 线 2i + 2 包含代理 i的排列 A_i,用空格分隔。
输出
在第一行,以整数形式输出身份验证成功的最大代理数。
第二行,输出按字典顺序最小的完整密码 S 达到这个最大值,如 L 由空格分隔的整数。
示例输入 1
2 3 4 0 2 0 1 1 2 3 1 2 1 3 2 1 3 2 2 3 1
示例输出 1
2 1 2 3 1
示例输入 2
3 2 5 0 0 1 0 2 1 1 1 2 2 2 1 2 2 1 1 2 1 2 1 2 2 1 1 2 1
示例输出 2
1 1 1 1 2 2
示例输入 3
5 5 12 0 3 0 0 5 1 0 2 0 0 4 0 1 3 2 4 5 1 2 2 3 4 4 5 2 3 4 5 1 2 1 1 5 4 3 3 2 5 1 4 2 1 3 5 2 4 5 3 5 1 5 1 4 2 4 3 4 1 5 4 3 2 1 3 4 2 2 1 5 1 3 2 5 5 4 3 1 2 5 4 4 5 3 4 2 2 5 1 1 2 3 3 4 5 1 3 2
示例输出 3
1 1 3 2 4 5 1 2 2 3 4 4 5
示例输入 4
8 8 40 0 2 0 4 0 6 0 8 1 0 3 0 5 0 7 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 0 2 4 6 8 0 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 1 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 1 2 3 4 5 6 7 8 1 3 5 7 2 4 6 8 2 4 6 8 1 3 5 7 2 4 6 8 1 3 5 7 2 4 6 8 1 3 5 7 2 4 6 8 1 3 5 7 2 4 6 8 1 3 5 7 4 1 2 3 8 5 6 7 5 1 6 2 7 3 8 4 5 1 6 2 7 3 8 4 5 1 6 2 7 3 8 4 5 1 6 2 7 3 8 4 5 1 6 2 7 3 8 4 5 6 7 8 1 2 3 4 1 2 1 4 2 6 3 8 1 4 3 6 5 8 7 2 4 1 6 2 8 3 1 4 2 5 3 6 4 7 5 8 6 1 2 4 6 8 7 5 2 1 4 3 6 5 8 7 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8 3 4 1 2 7 8 5 6 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 1 1 1 1 2 2 2 2 3 4 5 6 7 8 1 2 1 2 3 4 5 6 7 8
示例输出 4
1 1 2 1 4 2 6 3 8 1 4 3 6 5 8 7 2 4 1 6 2 8 3 1 4 2 5 3 6 4 7 5 8 6 1 2 4 6 8 7 5
示例输入 5
1 1 1 0 1 1
示例输出 5
1 1