H - 部屋割り Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君たちは、合宿で、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