#P1365. WJMZBMR打osu! / Easy

WJMZBMR打osu! / Easy

题目背景

原 维护队列 参见 P1903

题目描述

某一天WJMZBMR在打osu~~~但是他太弱逼了,有些地方完全靠运气:(

我们来简化一下这个游戏的规则

nn 次点击要做,成功了就是 o,失败了就是 x,分数是按 combo 计算的,连续 aa 个 combo 就有 a×aa\times a 分,combo 就是极大的连续 o

比如ooxxxxooooxxx,分数就是 2×2+4×4=4+16=202 \times 2 + 4 \times 4 = 4 +16=20

Sevenkplus 闲的慌就看他打了一盘,有些地方跟运气无关要么是 o 要么是 x,有些地方 o 或者 x 各有 50%50\% 的可能性,用 ? 号来表示。

比如 oo?xx 就是一个可能的输入。 那么 WJMZBMR 这场 osu 的期望得分是多少呢?

比如 oo?xx 的话,?o 的话就是 oooxx99),是x的话就是 ooxxx44),期望自然就是 (4+9)/2=6.5(4+9)/2 =6.5 了。

输入格式

第一行一个整数 nnn3×105n\le3\times10^5),表示点击的个数

接下来一个字符串,每个字符都是 ox? 中的一个

输出格式

一行一个浮点数表示答案

四舍五入到小数点后 44

如果害怕精度跪建议用 long double 或者 extended。

4
????
4.1250