← 返回题目列表

AtCoder · abc376_b

D. 手环(简单)

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

分数: 250 点

问题陈述

注:该问题与问题F的设置几乎相同,仅正文中粗体部分和约束条件有所不同。

您双手拿着一枚戒指。 该环由 N\ (N \geq 3) 零件编号 1,2,\dots,N,其中零件 i 和 i+1 (1 \leq i \leq N-1) 是相邻的,并且零件 1 和 N 也相邻。

最初,您的左手握住零件 1,并且你的右手拿着部分 2。 合而为一 操作,您可以执行以下操作:

  • 将你的一只手移至其当前握持的部分的相邻部分。但是,只有当另一只手不在目标零件上时,您才能执行此操作。

下图显示了初始状态以及可以和不能从该状态进行的操作示例。戒指每个部分上写的数字代表零件编号,标记为 L 和 R 的圆圈分别代表您的左手和右手。

您需要遵循 Q 按顺序向您提供说明。 的 i-th (1 \leq i \leq Q) 指令由字符表示 H_i 和一个整数 T_i,含义如下:

  • 执行一定数量的操作(可能为零),以便您的左手(如果 H_i is L)或你的右手(如果 H_i is R) 正在持有部分 T_i。 在这里,你 不得 移动未指定的另一只手 H_i.

保证只给出可实现的指令。

详细信息 在本题的设定下,可以证明,在跟随之前,双手的位置是唯一确定的 i每个指令 i。 此时,如果我们将左右手的位置表示为零件 l_i 和 r_i分别保证 T_i \neq r_i 当 H_i is L,和 T_i \neq l_i 当 H_i is R.


找出遵循所有指令所需的最少操作总数。

约束

  • 3 \leq N \leq 100
  • 1 \leq Q \leq 100
  • H_i is L or R.
  • 1 \leq T_i \leq N
  • N, Q,和 T_i 是整数。
  • 仅给出可实现的说明(有关详细信息,请参阅问题陈述)。

输入

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

N Q
H_1 T_1
H_2 T_2
\vdots
H_Q T_Q

输出

打印遵循所有说明所需的最少操作总数。


示例输入 1

6 3
R 4
L 5
R 6

示例输出 1

8

通过执行以下操作,您可以遵循所有 Q 按顺序说明。

  1. 将右手作为一部分移动 2 \rightarrow 3 \rightarrow 4 遵循第一条指令。
  2. 将左手作为一部分移动 1 \rightarrow 6 \rightarrow 5 遵循第二条指令。
  3. 将右手作为一部分移动 4 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 6 遵循第三条指令。

在这种情况下,操作总数为 2+2+4=8,这是最小值。 (请注意,在执行第三条指令时,您不能将右手作为一部分移动 4 \rightarrow 5 \rightarrow 6.)


示例输入 2

100 2
L 1
R 2

示例输出 2

0

在某些情况下,您可以按照说明进行操作而不执行任何操作。


示例输入 3

30 8
R 23
R 26
R 29
L 20
R 29
R 19
L 7
L 16

示例输出 3

92