/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 7 点
注意
この問題に対する言及は、2020/11/8 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
左右方向一列に並ぶ N 個のマスがあります。左から i 番目のマスをマス i と呼ぶことにします。
いくつかのマスには忍者がいて、その配置は文字列 S として与えられます。 S の i 番目の文字が # のときマス i には忍者がいて、 . のときマス i には忍者がいません。
今からタイプ A とタイプ B の 2 種類の操作を任意の順序で何回か行うことができます。一回も操作を行わなくても構いません。
- タイプ A : マス 1 以外に現在いる全ての忍者は、自分の一つ左のマスに分身を作る。分身は以後本物同様に扱われる。
- タイプ B : マス N 以外に現在いる全ての忍者は、自分の一つ右のマスに分身を作る。分身は以後本物同様に扱われる。
タイプ A を行う回数を x 、タイプ B を行う回数を y とします。
全ての操作の終了後、全てのマスに少なくとも一人の忍者がいるような手順のうち、x + y が最小になるような手順における x, y を一つ求めてください。
制約
- 1 \le N \le 50
- N は整数
- S は
.と#からなる。 - S には少なくとも 1 つ
#が含まれる。
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
タイプ A を行う回数を x 、タイプ B を行う回数を y としたとき、x + y が最小になるような手順における x, y を一つ、空白区切りで出力せよ。
入力例 1
5 .#..#
出力例 1
1 1
例えばタイプ A, タイプ B の順に行うと、各マスの忍者の有無は .#..# -> ##.## -> ##### と変化し、最終的に全てのマスに忍者が存在するようになります。
タイプ A とタイプ B の合計回数が 2 未満で目的を達成することはできないのでこれは答えの一つです。
他にも例えば 2 0 は正しい答えです。
入力例 2
6 ..#...
出力例 2
2 3
これは唯一の正しい答えです。
入力例 3
3 ###
出力例 3
0 0
全く分身しなくて良い場合もあります。
Score : 7 points
Warning
Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
There are N squares arranged in a row from left to right. Let Square i be the i-th square from the left.
There are ninjas in some squares. The positions of the ninjas are given as a string S. If the i-th character of S is #, there is a ninja in Square i; if that character is ., there is no ninja in Square i.
We can now do two types of operations, A and B, any number of times, possibly zero, in any order.
- Type A: Every ninja who is not in Square 1 creates his clone in the square to the immediate left of him. The clone will be treated as a real ninja from then on.
- Type B: Every ninja who is not in Square N creates his clone in the square to the immediate right of him. The clone will be treated as a real ninja from then on.
Let x and y be the numbers of times the operations of Type A and B are performed, respectively. Consider the sequences of operations after which there is at least one ninja in every square. Find x and y in one of those sequences of operations that minimizes x + y.
Constraints
- 1 \le N \le 50
- N is an integer.
- S consists of
.and#. - S contains at least one
#.
Input
Input is given from Standard Input in the following format:
N S
Output
Print x and y in a sequence of operations that minimizes x + y, with space in between, where x and y are the numbers of times the operations of Type A and B are performed, respectively.
Sample Input 1
5 .#..#
Sample Output 1
1 1
For example, if we first do Type A and then Type B, whether each square contains a ninja changes as follows: .#..# -> ##.## -> #####, and every square contains ninja eventually.
It is impossible to achieve this objective with less than two operations in total, so this is a valid answer.
There are also other valid answers; one of them is 2 0.
Sample Input 2
6 ..#...
Sample Output 2
2 3
This is the only valid answer.
Sample Input 3
3 ###
Sample Output 3
0 0
It is possible that no cloning is needed.