← 返回题目列表

AtCoder · code_festival_final_h

H. 房间分配

中文机器翻译题面 查看原题

問題文

高桥君和他的朋友们在训练营。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