← 返回题目列表

AtCoder · utpc2023_f

F. 翻转与否

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

配点 : 100 点

問題文

N 张卡片排成一行。 最初,当字符串为 S 可以得到第 i 第一个字母是 1 时,从左数第 i 张卡片是正面朝上,0 时是背面朝上。

您可以执行以下操作 您可以执行此操作超过 10^6 次。 交换

  • 将最右边的卡片移到最左边。之后,如果移动的卡片是正面朝上,则从左数 A_1,A_2,\dots,A_P 张牌的正反面全部翻转。然后,从左数第 B_1,B_2,\dots,B_Q 张牌,可以选择全部翻转其正反面,或者什么也不做。操作

的结果,希望字符串 T 可以得到第 i 第一个字母是 1 时,从左数第 i 张卡片是正面朝上,0 的牌是背面朝上。判定在不超过

10^6 次操作的情况下能否满足条件,如果可以满足条件,则选择操作次数最少的操作序列。如果无论怎样在不超过 1 请输出一个。

制約

  • 所有输入数字均为整数
  • 1 \leq N \leq 5000
  • S, T 是 您也可以写 0, 1 组成的长度 N 的字符串所需的时间.在这次比赛中,参赛者按照以下条件进行打字.
  • S \neq T
  • 1 \leq P, Q \leq N
  • 1 \leq A_1 < A_2 < \dots < A_P \leq N
  • 1 \leq B_1 < B_2 < \dots < B_Q \leq N

入力

输入是按以下格式从标准输入给出的。

N
S
T
P
A_1 A_2 \dots A_P
Q
B_1 B_2 \dots B_Q

出力

10^6 次操作的情况下都无法满足条件,-1 。 如果满足条件是可能的,请按照以下格式输出操作次数最少的操作序列。 1 输出一。

M
U

这里 M 表示操作次数,U 表示操作序列的长度, 第 M 可以得到第 0, 1 组成的字符串。 U 可以得到第 i 第一个字母是 1 时,i 次操作表示从左起 将第 B_1,B_2,\dots,B_Q 张卡片的正反面全部翻转,0 表示什么都不做。 在第


入力例 1

5
00001
00111
3
1 2 3
2
3 5

出力例 1

4
1001

1 次操作中,首先将最右边的卡片移到最左边后,卡片的状态变为 10000 ,由于移动的卡片正面朝上,因此翻转从左起第 A_1,A_2,A_3 枚目(1,2,3 张卡片的正反面后变为 01100 。之后,如果选择翻转从左起第 B_1,B_2 枚目(3,5 张卡片的正反面,则变为 01001 。 以后按照输出示例进行操作,2 关于第二次操作 01000 属于3 关于第二次操作 00100 属于4 关于第二次操作 00111 。 由于不存在比这更少操作次数的方法,因此输出示例是正确的输出。


入力例 2

4
0110
1000
2
1 2
4
1 2 3 4

出力例 2

-1

无论如何操作 10^6 都无法在以下次数内满足条件,-1 。