← 返回题目列表

Codeforces · 883/D

D. 包装工的反击

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

游戏场由 n 个方形单元格组成的线表示。有些牢房里有包装工,有些牢房里有星号,其余的牢房是空的。包装工吃星号。

在游戏开始之前,您可以为每个包装工选择向左或向右的移动方向。游戏开始后,所有包装工同时开始按照他们的指示移动。包装工无法改变给定的方向。

一旦包装工进入包含星号的单元格,包装工就会立即吃掉星号。一旦包装工离开牢房,牢房就空了。每个包装工以每秒 1 个细胞的速度移动。如果打包员进入边界单元,打包员就会停下来。打包员不干扰其他打包员的行动;在一个牢房中,可以有任意数量的包装工向任意方向移动。

你的任务是为每个包装工分配一个方向,以便他们吃掉最大数量的星号。如果有多种方法来指定吃掉最大数量星号的方向,您应该选择最短时间的方法。

输入

第一行包含整数 n (2 ≤ n ≤ 1 000 000) — 游戏区域中的单元格数量。

第二行包含 n 个字符。如果第 i 个字符是“.”,则第 i 个单元格为空。如果第 i 个字符是“*”,则第 i 个单元格包含星号。如果第 i 个字符是“P”,则第 i 个单元格包含一个 packman。

该字段包含至少一个星号和至少一个打包员。

输出

打印两个整数——包装工可以吃的星号的最大数量和完成它的最短时间。

示例

输入 #1

6
*.P*P*

输出 #1

3 4

输入 #2

8
*...P..*

输出 #2

1 3

注意

在第一个示例中,最左边的包装工应该向右移动,最右边的包装工应该向左移动。所有的星号都会被吃掉,最后一个星号会在4秒后被吃掉。