← 返回题目列表

AtCoder · joi2021_yo2_a

A. 圆形双六

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

配点: 100 点

問題文

JOI高中生葵购买了新的双六。这个双六是 它具有水平排列的 N+2 正方形形状。这些方格按照从最左边的方格到最右边的方格的顺序填充。 它们的编号最大为0 如果要将其更改为输出最多为 N+1 。起初,质量 0 和正方形 N+1 有 X 是质量 i (1 \leqq i \leqq N) 是 写入 S_i 。然而,S_i 是一个字符 . 或 如果 # 是。

葵是这个双六 1 我正在演奏两首曲子。一开始,棋子是正方形的。 A (1 \leqq A \leqq N) 面向右侧。然而,S_A 是一个字符 . 。葵是 1 每秒将棋子朝其面向的方向移动。 1 移动方块。

这个双六有以下内容规则 设置。 当棋子落在写有

  • X 的方块上时,棋子的方向就会反转。 即使棋子落在写有
  • . 的正方形上,也不会发生任何事情。 当棋子落在写有
  • # 的方块上时,棋子的方向就会反转。这时,这个方格上写的字符是 将其更改为 . 。因此,即使此后棋子落到这个方格上,方向也不会逆转。

请注意,翻转碎片和更改字母所需的时间可以忽略不计。

考虑到双六和棋子的初始状态, 编写一个程序,求直到所有写有# 的方块消失所需的时间。

制約

  • 2 \leqq N \leqq 200\,000.
  • 1 \leqq A \leqq N.
  • S_i 是一个字符 . 或 如果 # (1 \leqq i \leqq N).
  • S_A 是一个字符 . 是。
  • S_i 是一个字符 # 似乎是 i (1 \leqq i \leqq N) 至少 1 有两个。

小課題

  1. (40 点) N \leqq 3\,000.
  2. (60 点)没有额外的限制。

入力

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

N A
S

但是,S 是长度 字符串 N 。 i 文字目 (1 \leqq i \leqq N)是 S_i 是。

出力

在标准输出上, 计算所有带有# 的方块消失需要多少秒。 输出为 1 行。


入力例 1

7 3
.#.#..#

出力例 1

8

随着时间的推移,双六的状态发生如下变化。然而,朝右的棋子所在的方格是 >,放置朝左棋子的方格 由 < 代表。

  1.  X.#>#..#X
  2.  X.#.<..#X
  3.  X.#<...#X
  4.  X.>....#X
  5.  X..>...#X
  6.  X...>..#X
  7.  X....>.#X
  8.  X.....>#X
  9.  X......<X

因此,8 以秒为单位 所有写有 # 的方块都会消失,所以8 。


入力例 2

4 1
.#.#

出力例 2

7

随着时间的推移,双六的状态发生如下变化。

  1.  X>#.#X
  2.  X.<.#X
  3.  X<..#X
  4.  >...#X
  5.  X>..#X
  6.  X.>.#X
  7.  X..>#X
  8.  X...<X

因此,7 以秒为单位 所有写有 # 的方块都会消失,所以7 。


入力例 3

6 6
#####.

出力例 3

35