← 返回题目列表

AtCoder · arc172_f

F. 步行

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

分数: 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 X or Y.
  • 每个 t_1, t_2, \dots, t_N is X or Y.

输入

输入由标准输入按以下格式给出:

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