v

v.cpp/in/out

• 时间限制：3.0s
• 空间限制：512MB

题目描述

有 $n$ 个球排成一行，每个球的颜色为黑或白。

执行 $k$ 次操作，第 $i\ (1 \le i \le k)$ 次操作形式如下：

• 从 $[1, n-i+1]$ 中，等概率随机选择一个整数 $x$。
• 移除从左往右数的第 $x$ 个球，或从右往左数的第 $x$ 个球（也就是从左往右数的第 $n-i+2-x$ 个）。之后，所有右侧的球的编号减 1。

给定每个球的颜色信息，希望最大化移除的白球数量。

输出在最优策略下，期望的移除白球数量。误差在 $10^{-6}$ 范围内，即算正确。

输入格式

从文件 v.in 中读入数据。

第一行，两个整数 $n, k$。

第二行，一个长度为 $n$、仅由 W 和 B 组成的字符串，第 $i$ 个字符代表第 $i$ 个球的颜色，W 为白色，B 为黑色。

输出格式

输出到文件 v.out 中。

输出一行，一个浮点数，代表答案。

样例 1 输入

3 1
BWW

样例 1 输出

1.0000000000

样例 1 解释

如果 $x = 1$，从右侧操作，如果 $x = 2$ 或 $3$，从左侧操作，均可以移除一个白球。

样例 2 输入

4 2
WBWB

样例 2 输出

1.5000000000

数据范围

保证 $1 \le n \le 30$，$0 \le k \le n$。