← 返回题目列表

Codeforces · 847/E

E. 包装工

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

游戏场是一条 1 × n 的方形单元格。在某些单元格中,有包装工,在某些单元格中,有星号,其他单元格是空的。

Packman可以在1个时间单位内移动到相邻的小区。如果目标细胞中有星号,那么帕克曼就会吃掉它。帕克曼没有花任何时间去吃星号。

在最初的时刻,所有包装工都开始移动。每个Packman可以无限次地改变其移动方向,但不允许超出游戏场地的边界。打包员不干扰其他打包员的行动;在一个牢房中,可以有任意数量的包装工向任意方向移动。

你的任务是确定包装工可以吃掉所有星号的最短可能时间。

输入

第一行包含一个整数 n (2 ≤ n ≤ 105) — 游戏场的长度。

第二行包含由n个符号组成的游戏字段的描述。如果有符号“.”在位置 i — 单元格 i 是空的。如果位置 i 中有符号“*”,则单元格 i 中包含一个星号。如果位置 i 中有符号“P”——Packman 在单元格 i 中。

保证比赛场上至少有一名打包工和至少一名星号。

输出

打印包装工可以吃掉所有星号的最短可能时间。

示例

输入 #1

7
*..P*P*

输出 #1

3

输入 #2

10
.**PP.*P.*

输出 #2

2

注意

在第一个示例中,位置 4 的 Packman 将向左移动并吃掉位置 1 的星号。他将在其上花费 3 个时间单位。在相同的 3 个时间单位内,位于位置 6 的帕克曼将吃掉带有星号的相邻两个单位。例如,它可以向左移动并在位置5(1个时间单位)吃星号,然后从位置5向右移动并在位置7(2个时间单位)吃星号。因此,在 3 个时间单位内,Packmen 将吃掉游戏场上的所有星号。

在第二个示例中,位置 4 的 Packman 将向左移动,2 个时间单位后将吃掉位置 3 和 2 的星号。位置 5 和 8 的 Packman 将向右移动,2 个时间单位后将分别吃掉位置 7 和 10 的星号。所以2个时间单位足以让Packmen吃掉游戏场上的所有星号。