422. Fast Typing
Time limit per test: 0.25
Memory limit: 262144
Vasya has little experience in typing, thus he has to look at the keyboard to locate the necessary keys, and still makes typos while doing so. For simplicity sake, we'll assume that the only type of typo he makes is replacing a character by another one. To correct those, he employs the following strategy: from time to time, he looks at the screen, and if there is any typo in the text, he removes all the characters from the end of the text to the first typo he made inclusive (i.e., he leaves only the correct part of the text intact) by pressing 'backspace' key several times, and continues typing from that position again.
Pressing any key (including 'backspace') takes 1 unit of time, and looking at the screen takes t
units of time. Given the probabilities of making an error for each character in the text, compute the minimal possible expected time to type the entire text correctly (including verifying that by looking at the screen in the end and noticing no typos).
The text is n
characters long, and the probability of mistyping i
-th character is equal to ai
The input file contains two integer numbers n
(1 ≤ n
≤ 3000, 1 ≤ t
), followed by n
real numbers ai
Output one real number — the minimal possible expected time. Your answer will be considered correct if it is within 10-6
relative error of the exact answer.
0.00001 0.5 0.00001