問題一覧 > 通常問題

No.667 Mice's Luck(ネズミ達の運)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-6}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 316
作問者 : butsurizukibutsurizuki / テスター : はむこはむこ
1 ProblemId : 1439 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-03-24 00:00:50

問題文

$N$匹のネズミ達は、住み処になりそうな$N$個の箱が並んでいるのを見つけました。
しかし、それは罠でそのうちのいくつかにネズミ捕りが仕掛けられていました。
ネズミ達はそれに気づきましたが、他に住み処も見つからないので泣く泣く入ることにしました。
ネズミ達は最初は$N$個の箱のうちの何個が安全で、何個が罠かという情報のみ知っています。
そこから$i(1 \le i \le N)$番目のネズミが$i$番目の箱に入っていきます。
$i+1$番目以降のネズミには$i$番目のネズミの安否を知ることが出来ます。
貴方の使命は、ネズミ達に(ネズミ達が知り得る情報だけを元にした)ネズミ捕りに捕られず助かる確率を教えてあげることです。

貴方には長さ$N$の文字列$S$が与えられます。
文字列$S$の$i$文字目が'o'なら$i$番目の箱は安全で、'x'ならその箱にネズミ捕りが仕掛けられています。

例えば$S$が"ooxxoxx"の場合、
1番目のネズミにはoが3つ、xが4つ残されているので助かる確率は42.85714%です。
1番目のネズミが助かり残るはoが2つ、xが4つ残されているので2番目のネズミが助かる確率は33.33333%です。
2番目のネズミが助かり残るはoが1つ、xが4つ残されているので3番目のネズミが助かる確率は20.00000%です。
3番目のネズミが捕られ残るはoが1つ、xが3つ残されているので4番目のネズミが助かる確率は25.00000%です。
4番目のネズミが捕られ残るはoが1つ、xが2つ残されているので5番目のネズミが助かる確率は33.33333%です。
5番目のネズミが助かりxが2つのみ残されているので6番目のネズミが助かる確率は0.00000%です。
6番目のネズミが助かりxが1つのみ残されているので7番目のネズミが助かる確率は0.00000%です。
イメージ

入力

$S$

文字列$S$が1行に与えられます。
・制約
文字列$S$は'o','x'のみで構成される
$1 \le S$の長さ$= N \le 10^5$

出力

$P_1$
$P_2$
$\dots$
$P_N$

$P_i$を$i$番目のネズミが助かる確率(%)とし、$N$行出力してください。
$0.000001=10^{-6}$以下の誤差は許容されます。
出力の最後に改行が必要です。

サンプル

サンプル1
入力
ooxxoxx
出力
42.8571428571429
33.3333333333333
20.0000000000000
25.0000000000000
33.3333333333333
0.0000000000000
0.0000000000000

問題文中の例です。%単位で出力することに注意してください。
この例では小数第13位まで正しい値を算出していますが、実際は$10^{-6}$以下の誤差は許容されます。

サンプル2
入力
xxxxxxxxxx
出力
0.0000000000000
0.0000000000000
0.0000000000000
0.0000000000000
0.0000000000000
0.0000000000000
0.0000000000000
0.0000000000000
0.0000000000000
0.0000000000000

残念ながら全てのネズミが助からないことを悟っています。

サンプル3
入力
xxooxoxxxxoxoxxoooxo
出力
45.0000000000000
47.3684210526316
50.0000000000000
47.0588235294118
43.7500000000000
46.6666666666667
42.8571428571429
46.1538461538462
50.0000000000000
54.5454545454545
60.0000000000000
55.5555555555556
62.5000000000000
57.1428571428571
66.6666666666667
80.0000000000000
75.0000000000000
66.6666666666667
50.0000000000000
100.0000000000000

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。