No.667 Mice's Luck(ネズミ達の運)
タグ : / 解いたユーザー数 324
作問者 : butsurizuki / テスター : はむこ
問題文
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。