Колода для рівноваги

Щоб накопичити грошей на нове стійло у своєму хліві, корова Бессі почала виступати в місцевому цирку, демонструючи свою неймовірну здатність до балансування, обережно пересуваючись туди-сюди по піднятому колоді для рівноваги!

Сума грошей, яку Бессі заробляє за своє виступ, залежить від того, в якому місці вона зрештою зістрибне з колоди. Позиції на колоді позначені $0$, $1$, $\dots$, n + 1 зліва направо. Якщо Бессі коли-небудь опиняється на позиції $0$ або n + 1, вона падає з одного з кінців колоди і, на жаль, не отримує жодної оплати.

Коли Бессі знаходиться на позиції $k$, вона може зробити одне з наступного:

1. Підкинути монетку. Якщо випаде "решка", вона переміщується на позицію k - 1; якщо випаде "орел", вона переміщується на позицію k + 1 (тобто кожен результат трапляється з ймовірністю $1/2$).

2. Зістрибнути з колоди та отримати оплату f(k)~(0 \le f(k) \le 10^9).

Бессі розуміє, що не може гарантувати собі конкретну оплату, оскільки її рух визначається випадковими підкиданнями монетки. Однак для кожної початкової позиції вона хоче визначити свою очікувану оплату, якщо вона прийматиме оптимальну послідовність рішень (тобто рішень, які призводять до найвищої можливої очікуваної оплати). Наприклад, якщо її стратегія приносить їй оплату $10$ з ймовірністю $1/2$, $8$ з ймовірністю $1/4$ та $0$ з ймовірністю $1/4$, то її очікувана оплата є зваженим середнім 10 \cdot (1/2) + 8 \cdot (1/4) + 0 \cdot (1/4) = 7.