分数: 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
可能不需要克隆。