У вас есть полоска бумаги \(s\), которая имеет длину \(n\) ячеек. Каждая ячейка может быть либо черной, либо белой. За одну операцию вы можете выбрать любые \(k\) последовательных ячеек и сделать их все белыми.
Найдите минимальное количество операций, необходимых для удаления всех черных ячеек.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество операций, необходимых для удаления всех черных ячеек.
Примечание
В первом наборе входных данных примера вы можете выполнить следующие операции: \(\)\color{red}{\texttt{WBW}}\texttt{WWB} \to \texttt{WWW}\color{red}{\texttt{WWB}} \to \texttt{WWWWWW}\(\)
Во втором наборе входных данных примера вы можете выполнить следующие операции: \(\)\texttt{WW}\color{red}{\texttt{BWB}}\texttt{WW} \to \texttt{WWWWWWW}\(\)
В третьем наборе входных данных примера вы можете выполнить следующие операции: \(\)\texttt{B}\color{red}{\texttt{WBWB}} \to \color{red}{\texttt{BWWW}}\texttt{W} \to \texttt{WWWWW}\(\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
6 3
WBWWWB
7 3
WWBWBWW
5 4
BWBWB
5 5
BBBBB
8 2
BWBWBBBB
10 2
WBBWBBWBBW
4 1
BBBB
3 2
WWW
|
2
1
2
1
4
3
4
0
|