题目描述

Fedor is an avid traveler. As a result of his hobby, he has gathered a big collection of postcards from all over the world. Each postcard has a unique picture on the front side and some fields for address information and text on the back side.

During one of the parties at Fedor's house, he decided to show all his of postcards to the guests. To achieve that, he wants to lay them all out on the table. Initially, all of his postcards are arranged in a single stack that Fedor is holding in his hands. Unfortunately, some of the postcards in that stack can be turned incorrectly -- upside down. Ideally, Fedor would like all postcards on the table to lie with the picture on top, but looking at every postcard and turning it over individually can be very time-consuming. Instead, he came up with the following process:

Let $n$ be the number of postcards remaining in the stack in his hands. Fedor chooses a random number $k$ uniformly between $1$ and $n$ and takes top $k$ postcards from the stack.

He looks at the topmost postcard among these $k$ postcards. If it is oriented in the wrong way, he turns the whole stack of $k$ postcards upside down together.

He then puts these $k$ postcards on the table without any further rotations.

If there are still some postcards remaining in the stack in his hands, Fedor goes back to step $1$ .

Of course, after all the postcards are on the table, there might still be some that lie back side up. What is the expected number of such postcards?

输入格式

The input consists of a single line of C and W characters -- i-th character corresponds to i-th postcard in the stack, counting from the top of the stack. C means that i-th postcard is oriented correctly in the initial stack, and W means that i-th postcard is oriented in the wrong way. The number of characters is between $1$ and $10^{6}$ inclusive.

输出格式

Output one real number -- the expected number of incorrectly placed postcards on the table. The absolute or relative error should not exceed $10^{−9}$ .

题目大意

题目描述

费多是个热心的旅行者。由于他的爱好，他收集了来自世界各地的大量明信片。每张明信片正面都有一张独特的图片，背面有一些地址信息和文本字段。

在费多家的一次聚会上，他决定向客人展示他所有的明信片。为了实现这一目标，他想把它们全部摆在桌面上。起初，他所有的明信片都被安排在一个单叠里，费多拿在手里。不幸的是，这堆明信片中的一些可能会被错误地翻过来——颠倒过来。理想情况下，费多希望桌上的所有明信片都放在图片的上方，但查看每张明信片并逐个翻转可能非常耗时。相反，他提出了以下过程：

让 $n$ 是他手中的那堆明信片的剩余数量。费多均匀地选择一个介于1和 $n$ 之间的随机数 $k$ ，并从堆栈中取出前 $k$ 张明信片。

他看了看这 $k$ 张明信片中最上面的一张明信片。如果方向错误，他会将整叠明信片倒置在一起。

然后，他把这 $k$ 张明信片放在桌子上，不再旋转。

如果他手里还有一些明信片，费多会返回到步骤 $1$ 。

当然，在所有的明信片都放在桌子上之后，可能仍然有一些明信片是倒着放的。这类明信片的预期数量是多少？

输入格式

输入由一行 $C$ 和 $W$ 字符组成——第 $i$ 个字符对应于栈中的第 $i$ 个明信片，从栈顶部开始计数。$C$ 表示第 $i$ 张明信片在初始栈中的方向正确， $W$ 表示第 $i$ 张明信片的方向错误。字符数在 $1$ 到 $10^{6}$ 之间, $6$ 包括在内。

输出格式

输出一个实数——表上错误放置的明信片的预期数量。绝对或相对误差不应超过 $10^{−9}$

说明/提示

时间限制：2s，内存限制：512 MB。

CWCC

1.0

WWCWCCW

2.333333333333

提示

Time limit: 2 s, Memory limit: 512 MB.

spj 由 tiger2005 提供。