AtCoder Regular Contest 040
B
直線塗り
AtCoder
⌀ 1113
原题
← AC →
翻译中…

Problem Statement

翻译中…

イカの高橋君は床を塗るのが大好きです。床は $N$ 個のマスが左右に $1$ 列に並んでいるような形をしています。左から $i$ 個目のマスをマス $i$ と呼ぶことにします。すでにいくつかのマスは塗られていますが、いくつかのマスは塗られていません。高橋君はインクを発射できる射程が $R$ の銃を使って全てのマスを塗ろうとしています。高橋君は最初マス $1$ にいます。そして、$1$ 秒の間に以下のいずれか $1$ つの行動が行えます。

翻译中…
  • $1$ つ右のマスに移動する。すなわち、マス $i$ からマス $i+1$ に移動する。ただし、マス $N$ にいるときは行えない。
  • 銃を撃って床を塗る。マス $i$ にいるときに銃を撃つと、マス $i$ からマス $i+R-1$ までのマスを全て塗ることができる。ただし、$i+R-1$ が $N$ より大きい場合は、マス $i$ からマス $N$ までのマスが塗られる。
翻译中…

高橋君が全てのマスを塗るためにかかる時間の最小値を求めてください。

翻译中…

Input

翻译中…

入力はイカの形式で標準入力から与えられる。

翻译中…

N R
S

翻译中…
  • $1$ 行目には、マス目の個数を表す整数 $N (1 ≦ N ≦ 100)$ と銃の射程を表す整数 $R (1 ≦ R ≦ N)$ が空白区切りで与えられる。
  • $2$ 行目には、長さ $N$ の文字列 $S$ が与えられる。このうち $i (1 ≦ i ≦ N)$ 文字目は、マス $i$ の情報を以下のように表す。
  • . の場合:このマスがまだ塗られていないことを表す。
    • o の場合:このマスがすでに塗られていることを表す。
翻译中…

Output

翻译中…

高橋君が全てのマスを塗るためにかかる時間の最小値を $1$ 行に出力せよ。出力の末尾に改行を入れること。

翻译中…

样例

Input #1
7 3
...o.o.
Output #1
6
銃を撃つ → $4$ 歩前進 → 銃を撃つ、という行動をとると時間が最小となります。
Input #2
8 4
...o.ooo
Output #2
3
銃を撃つ → $1$ 歩前進 → 銃を撃つ、という行動をとると時間が最小となります。
Input #3
4 4
oooo
Output #3
0
最初から全てのマスが塗られています。
题目信息
题号
arc040_b
时间限制
2 s
内存限制
256 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。