{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cbr\u003eVasya 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\u0027ll 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 \u0027backspace\u0027 key several times, and continues typing from that position again.\u003cbr\u003ePressing any key (including \u0027backspace\u0027) takes 1 unit of time, and looking at the screen takes \u003ci\u003et\u003c/i\u003e 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).\u003cbr\u003eThe text is \u003ci\u003en\u003c/i\u003e characters long, and the probability of mistyping \u003ci\u003ei\u003c/i\u003e-th character is equal to \u003ci\u003ea\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e.\u003cbr\u003e\u003cdiv align\u003d\"left\" style\u003d\"margin-top: 1.0em;\"\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/div\u003eThe input file contains two integer numbers \u003ci\u003en\u003c/i\u003e and \u003ci\u003et\u003c/i\u003e (1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 3000, 1 ≤ \u003ci\u003et\u003c/i\u003e ≤ 10\u003csup\u003e6\u003c/sup\u003e), followed by \u003ci\u003en\u003c/i\u003e real numbers \u003ci\u003ea\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e (\u003cimg src\u003d\"CDN_BASE_URL/445371516a67a98c1236587f767c7bae?v\u003d1715982649\" style\u003d\"vertical-align: text-bottom;top: -2.0px;max-width: 100.0%;max-height: 100.0%;\"\u003e).\u003cbr\u003e\u003cdiv align\u003d\"left\" style\u003d\"margin-top: 1.0em;\"\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/div\u003eOutput one real number\u0026nbsp;— the minimal possible expected time. Your answer will be considered correct if it is within 10\u003csup\u003e-6\u003c/sup\u003e relative error of the exact answer.\u003cbr\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 1\n0.00001 0.5 0.00001\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8.000080000800008\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}