← 返回题目列表

Codeforces · 405/B

B. 多米诺骨牌效应

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

小克里斯知道玩多米诺骨牌没有什么乐趣,他认为这太随机了,不需要技巧。相反,他决定玩多米诺骨牌,进行一场“多米诺骨牌表演”。

Chris 将 n 块多米诺骨牌排成一行,将每块多米诺骨牌垂直放置。一开始,他同时将一些多米诺骨牌推向左侧或右侧。然而,在每两个朝同一方向推动的多米诺骨牌之间,至少有一个朝相反方向推动的多米诺骨牌。

每一秒之后,每张向左倒下的多米诺骨牌都会推动左侧相邻的多米诺骨牌。同样,向右倒下的多米诺骨牌会推动右侧相邻的多米诺骨牌。当多米诺骨牌从两侧倒在垂直的多米诺骨牌上时,由于力的平衡,它会保持静止。该图显示了该过程的一个可能的示例。

给定克里斯推动多米诺骨牌的初始方向,找出在该过程结束时留下垂直站立的多米诺骨牌的数量!

输入

第一行包含一个整数 n (1 ≤ n ≤ 3000),即该行中多米诺骨牌的数量。下一行包含长度为 n 的字符串 s。字符串 si 的第 i 个字符等于

- “L”,如果第 i 个多米诺骨牌已被推向左侧;
- “R”,如果第 i 个多米诺骨牌已被推到右侧;
- “.”,如果第 i 个多米诺骨牌尚未被推动。

保证如果 si = sj = "L" 且 i < j,则存在 i < k < j 且 sk = "R";如果 si = sj = "R" 且 i < j,则存在这样的 k:i < k < j 且 sk = "L"。

输出

输出一个整数,即过程结束时保持垂直的多米诺骨牌数量。

示例

输入 #1

14
.L.R...LR..L..

输出 #1

4

输入 #2

5
R....

输出 #2

0

输入 #3

1
.

输出 #3

1

注意

第一个示例案例如图所示。保持垂直站立的四块以橙色突出显示。

在第二个示例中,由于第一个棋子推倒了所有其他棋子,因此所有棋子都会掉落。

在最后一个示例中,单个部件没有被向任一方向推动。