問題文
高桥君和他的朋友们在训练营。N 人,K 您将住在一个房间里。
高桥等人, 我们准备了一张彩票,上面写着1 到 N 的数字,并决定从数字最小的开始决定入住哪个房间。
高桥的小组由喜欢安静房间的人和喜欢热闹房间的人组成。 有2 类型的人。
喜欢安静房间的人更喜欢人越少的房间。我决定留在迄今为止房间分配中人数最少的房间。
喜欢热闹房间的人更喜欢人越多的房间。根据目前的房间分配情况,我们将入住人数最多的房间。
对于这两类人,如果有多个符合条件的房间,则以等概率从符合条件的房间中进行选择。 1 选择一个房间并留在该房间。
高桥先生想要预测抽签结束后、实际分配房间之前,每个参与者将与多少人共享同一房间。
查找每个参与者住在同一房间的预期人数。请注意,入住同一间客房的人数包括本人。
入力
输入是从标准输入按以下格式给出的
N K S
- 1 行中显示参加训练营的人数。 N (1 ≦ N ≦ 200,000) 和房间数量 K (1 ≦ K ≦ 200,000) 用空格分隔。 在
- 2 行中,有一个字符串,代表训练营参与者是什么样的人的信息。 S(|S| = N) 是 在 1 行中给出。
- S 是
仅包含字符
0、1之一,i 第一个字符 S_i 但是抽奖 表示有关第 i 个人的信息。如果 S_i 是0,那么i 表示此人喜欢安静的房间,1表示此人喜欢热闹的房间。
出力
对于每个参与者,计算住在同一房间的预期人数。1 逐行 N 行。
i 行中,有抽奖。 输出 i 参与者住在同一房间的预期人数。
该误差是相对误差或绝对误差。 最多允许 10^{-6} 。 第
入力例1
7 3 1000011
出力例1
2.33333333333333 2.33333333333333 2.33333333333333 3 3 4 4
1,2,3 人是1,2,4 由于您将以相同的概率呆在一个房间中,因此期望值为 7/3 。
4,5 人是 2,4 由于您将以相同的概率呆在一个房间中,因此期望值为 3 。
6,7 人是 4 由于您将住在共用房间,因此预期值为 4 。
入力例2
12 5 000000101101
出力例2
2.4 2.4 2.4 2.4 2.4 6 6 2 6 6 2 6