UVA12411 A Dangerous Maze (II)

你置身于一个迷宫；起初你面前有 $n$ 扇门。你可以任意选择一扇门，每扇门被选择的概率相同。 如果你选择第 $i$ 扇门，它会在 $x _ i$ 分钟后要么将你带回起点，要么带你走出迷宫。如果你被带回起点，你会记住自己最近选择过的 $K$ 扇门。下次选择时，你绝不会选择已访问过的门。也就是说，你不会选择最近 $K$ 次所访问的门。剩余门被选择的概率仍然相等。 现在，你想求走出这个迷宫的期望时间。

输入以一个整数 $T$（$\le 100$）开头，表示测试用例的数量。 每个用例包含一个空行，接着是两个整数 $n$ 和 $K$（$1 \le n \le 100, 0 \le K \le n$）。下一行包含 $n$ 个以空格分隔的整数。如果第 $i$ 个整数 $x _ i$ 为正，则表示第 $i$ 扇门会在 $x _ i$ 分钟后将你带出迷宫；如果为负，则表示第 $i$ 扇门会在 $|x _ i|$ 分钟后将你带回起点。你可以认为 $1 \le |x _ i| \le 10000$。

对于每个测试用例，输出用例编号和走出迷宫的期望时间。如果无法走出迷宫，则输出 $\tt -1.000$；否则在计算结果上加上 $10 ^ {-9}$ 以避免精度误差后保留三位小数输出。