← 返回题目列表

AtCoder · awc0084_e

E. 密码转换设备和密码认证

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

分数: 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,按此顺序执行以下操作:

  1. 传输和身份验证检查:使用设备当前的转换规则 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的身份验证成功。
  2. 转换规则更新:无论认证是否成功,都会使用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