No.667 Mice's Luck
タグ : / 解いたユーザー数 340
作問者 :
butsurizuki
/ テスター :
はむこ
Problem Statement
$N$ mice found $N$ boxes lined up that looked like they could serve as homes.
However, it was a trap: mousetraps had been set in some of the boxes.
The mice noticed this, but since they could not find any other home, they reluctantly decided to enter.
Initially, the mice know only how many of the $N$ boxes are safe and how many are traps.
Then, the $i(1 \le i \le N)$-th mouse enters the $i$-th box.
The $i+1$-th and later mice can learn whether the $i$-th mouse is safe or not.
Your mission is to tell the mice the probability (based only on the information the mice can know) that they will survive without being caught by a mousetrap.
You are given a string $S$ of length $N$.
If the $i$-th character of the string $S$ is 'o', the $i$-th box is safe, and if it is 'x', a mousetrap is set in that box.
For example, if $S$ is "ooxxoxx",
for mouse 1, 3 o's and 4 x's remain, so its probability of surviving is 42.85714%.
Mouse 1 survives, leaving 2 o's and 4 x's, so the probability that mouse 2 survives is 33.33333%.
Mouse 2 survives, leaving 1 o and 4 x's, so the probability that mouse 3 survives is 20.00000%.
Mouse 3 is caught, leaving 1 o and 3 x's, so the probability that mouse 4 survives is 25.00000%.
Mouse 4 is caught, leaving 1 o and 2 x's, so the probability that mouse 5 survives is 33.33333%.
Mouse 5 survives, leaving only 2 x's, so the probability that mouse 6 survives is 0.00000%.
Mouse 6 survives, leaving only 1 x, so the probability that mouse 7 survives is 0.00000%.
Illustration
Input
$S$
The string $S$ is given on one line.
・Constraints
The string $S$ consists only of 'o' and 'x'
$1 \le S$'s length $= N \le 10^5$
Output
$P_1$ $P_2$ $\dots$ $P_N$
Let $P_i$ be the probability (%) that the $i$-th mouse survives, and output $N$ lines.
An error of at most $0.000001=10^{-6}$ is allowed.
A newline is required at the end of the output.
Sample
Sample 1
Input
ooxxoxx
Output
42.8571428571429 33.3333333333333 20.0000000000000 25.0000000000000 33.3333333333333 0.0000000000000 0.0000000000000
This is the example from the problem statement. Note that the output is in units of %.
This example computes the correct values up to the 13th decimal place, but in practice an error of at most $10^{-6}$ is allowed.
Sample 2
Input
xxxxxxxxxx
Output
0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000
Unfortunately, the mice realize that none of them will survive.
Sample 3
Input
xxooxoxxxxoxoxxoooxo
Output
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もしくは右上の雲マークをクリックしてアカウントを作成してください。