← 返回题目列表

AtCoder · past202010_d

D. 另一个自我

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

分数: 7 点

警告

2020 年 11 月 8 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

有 N 方块从左到右排成一排。让广场 i 是 i从左边算起第一个方格。 有些广场上有忍者。忍者的位置以字符串形式给出 S。如果 i- 第一个字符 S is #,广场上有一个忍者 i;如果该字符是 .,广场上没有忍者 i。 现在,我们可以以任意顺序执行任意次数(可能为零)的两种类型的操作 A 和 B。

  • A型:所有不在Square中的忍者 1 在他左边的方块中创建了他的克隆体。从此克隆人将被视为真正的忍者。
  • B型:所有不在Square中的忍者 N 在他右边的方块中创建了他的克隆体。从此克隆人将被视为真正的忍者。

让 x 和 y 分别是类型A和B的操作被执行的次数。 考虑每个方格中至少有一名忍者之后的操作顺序。查找 x 和 y 在这些操作序列之一中,最小化 x + y.

约束

  • 1 \le N \le 50
  • N 是一个整数。
  • S 包括 . 和 #.
  • S 包含至少一个 #.

输入

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

N
S

输出

打印 x 和 y 在一系列操作中最小化 x + y,中间有空格,其中 x 和 y 分别是类型A和B的操作执行的次数。


示例输入 1

5
.#..#

示例输出 1

1 1

例如,如果我们先做类型A,然后做类型B,则每个方格是否包含忍者会发生如下变化: .#..# -> ##.## -> #####,最终每个方格都包含忍者。 总共少于两次操作是不可能实现这个目标的,所以这是一个有效的答案。 还有其他有效的答案;其中之一是 2 0.


示例输入 2

6
..#...

示例输出 2

2 3

这是唯一有效的答案。


示例输入 3

3
###

示例输出 3

0 0

可能不需要克隆。