分数: 1000 点
问题陈述
AtCoder王国有 2N 交叉路口标有数字 1 to 2N。此外,还有以下三种类型 单向 王国的道路:
- A 型: 对于每个 2 \leq i \leq N,从路口有一条路 2i-3 到交叉路口 2i-1.
- B 型: 对于每个 2 \leq i \leq N,从路口有一条路 2i-2 到交叉路口 2i.
- C 型: 对于每个 1 \leq i \leq N,有一条道路连接路口 2i-1 和交叉路口 2i 有方向 s_i.
在这里, s_i is X or Y,其中方向 X 表示道路从交叉路口出发 2i-1 到交叉路口 2i和方向 Y 表示从交叉路口出发 2i 到交叉路口 2i-1.
高桥想要 步行 多次,以便对于每个 1 \leq i \leq N,Type-C道路连接路口方向 2i-1 和 2i 将是 t_i.
什么是散步?
从任意交叉路口开始,重复以下操作零次或多次:
- 如果可以从当前路口前往 Type-C 道路,则沿着 Type-C 道路步行到下一个路口。
- 否则,如果可以从当前路口前往 A 类或 B 类道路,则沿着该路步行到下一个路口。
然后,将所有经过的Type-C道路的方向反转。
计算实现目标所需的最少步行次数,并提供一种以最少步行次数实现目标的方法。在这个问题的约束下,可以证明在有限次数的游走中可以实现目标。
约束
- N 是一个整数,使得 1 \leq N \leq 4000.
- 每个 s_1, s_2, \dots, s_N is
XorY. - 每个 t_1, t_2, \dots, t_N is
XorY.
输入
输入由标准输入按以下格式给出:
N s_1 s_2 \cdots s_N t_1 t_2 \cdots t_N
输出
按以下格式打印您的解决方案,其中 X 是行走次数, i第次步行 (1 \leq i \leq X) 从交叉路口开始 a_i 并在交叉路口结束 b_i.
X a_1 b_1 a_2 b_2 \vdots a_X b_X
示例输入 1
5 XYXYX XXYXX
示例输出 1
1 2 7
在此示例输入中,Takahashi 将按如下方式行走:
- 从交叉路口开始 2.
- 由于没有 Type-C 道路可从交叉路口行驶 2,沿B型路步行至路口 4.
- 由于从交叉路口出发有一条 Type-C 道路 4,沿Type-C路步行至路口 3.
- 由于没有 Type-C 道路可从交叉路口行驶 3,沿A型路步行至路口 5.
- 由于从交叉路口出发有一条 Type-C 道路 5,沿Type-C路步行至路口 6.
- 由于没有 Type-C 道路可从交叉路口行驶 6,沿B型路步行至路口 8.
- 由于从交叉路口出发有一条 Type-C 道路 8,沿Type-C路步行至路口 7.
- 在交叉路口完成 7.
本次步行经过以下3条Type-C路:
- 连接路口的道路 3 和交叉路口 4.
- 连接路口的道路 5 和交叉路口 6.
- 连接路口的道路 7 和交叉路口 8.
这些道路的方向是相反的,因此连接交叉路口的道路的方向 2i-1 和 2i 为 i = 1, 2, 3, 4, 5 现在 X, X, Y, X, X分别实现目标。
示例输入 2
5 XXYYX XXYYX
示例输出 2
0
注意,一开始的目标就已经达到了,所以一次都不需要走。
示例输入 3
5 XXXXX YYYYY
示例输出 3
5 1 2 3 4 5 6 7 8 9 10
示例输入 4
20 XXXYXYYXXXYXXXXYYXXY XXYXYYXXYXXYXYXYXYXY
示例输出 4
5 14 18 29 38 14 26 5 10 27 35
示例输入 5
20 YXYXYXYYYXYYXYYXYXXX XXXXXYXYYYXYYXXYYYXY
示例输出 5
5 29 36 10 38 2 3 4 7 28 40