Problem E
IMO Harder Problem
After passing the final round of the Hunter Exam, Gon is now a Hunter! But before continuing his exciting journey, Gon decides to visit his home in ‘While Island’.
Aunt Mito is happy that Gon has become a Hunter and has visited home. But at the same time, she feels worried about Gon — the life of a Hunter is challenging. Thus, she will not allow Gon to leave ‘While Island’, unless Gon is able to solve a puzzle prepared by aunt Mito.
But what puzzle should Mito give to Gon? Mito opened ‘IMO 2019 Problems’ and found the following problem:
The Bank of Bath issues coins with an $H$ on one side and a $T$ on the other. Prof. Tuy has $n$ of these coins arranged in a line from left to right. He repeatedly performs the following operation: if there are exactly $k > 0$ coins showing $H$, then he turns over the $k$-th coin from the left; otherwise, all coins show $T$ and he stops. For example, if $n = 3$ the process starting with the configuration $THT$ would be: $THT \rightarrow HHT \rightarrow HTT \rightarrow TTT$, which stops after three operations.
Show that, for each initial configuration, Prof. Tuy stops after a finite number of operations.
‘This problem is too easy’ — Mito thought. ‘Gon will be able to solve it in no time’.
After some more thinking, Mito changed the above problem to the following harder version:
For each initial configuration $C$, let $L(C)$ be the number of operations before Prof. Tuy stops.
Given a sequence $S$ consisting of $H$, $T$ and $?$, representing some initial state, where $?$ denotes an unknown state. Calculate the average value of $L(C)$ over all possible sequences $C$ represented by $S$.
Even though Gon is smart, he is still unable to solve this question. Please help Gon!
Input
The input contains a single non-empty line with at most $10^6$ characters — the sequence $S$.
Output
The output must contain a single number — the average value of $L(C)$, as explained in the statement.
Your answer will be considered correct if its relative or absolute error doesn’t exceed $10^{-6}$.
Namely: let’s assume that your answer is $a$, and the answer of the jury is $b$. The checker program will consider your answer correct, if $\frac{|a-b|}{max(1,b)} \leq 10^{-6}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
HH |
2.0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
H? |
1.5 |
| Sample Input 3 | Sample Output 3 |
|---|---|
?? |
1.5 |
