Tarazlıq Lövhəsi

Tövləsindəki yeni dayanacaq üçün pul yığmaq məqsədilə inək Bessi yerli sirkdə çıxış etməyə başlayıb və hündür tarazlıq lövhəsi üzərində diqqətlə irəli-geri yeriyərkən heyrətamiz tarazlıq hissini nümayiş etdirir!

Bessinin çıxışı üçün qazandığı pul miqdarı, onun lövhədən haçan tullanacağından asılıdır. Lövhə üzərindəki mövqelər soldan sağa $0$, $1$, $\dots$, n + 1 ilə işarələnmişdir. Əgər Bessi hər hansı anda $0$ və ya n + 1 mövqeyinə çatarsa, lövhənin uclarından birindən düşür və təəssüf ki, heç bir ödəniş almır.

Bessi $k$ mövqeyində olduqda aşağıdakılardan birini edə bilər:

1. Pul atmaq. Əgər yazı gəlsə, k - 1 mövqeyinə keçir; əgər gerb gəlsə, k + 1 mövqeyinə keçir (yəni, hər bir nəticə $1/2$ ehtimalla baş verir).

2. Lövhədən tullanmaq və f(k)~(0 \le f(k) \le 10^9) ödənişini almaq.

Bessi başa düşür ki, hərəkəti təsadüfi pul atma nəticələri ilə idarə olunduğu üçün hər hansı konkret ödənişi təmin edə bilməz. Lakin, hər bir başlanğıc mövqeyi üçün, optimal qərarlar ardıcıllığı tətbiq etdiyi təqdirdə (yəni, ən yüksək mümkün gözlənilən ödənişə gətirib çıxaran qərarlar) gözlənilən ödənişini müəyyən etmək istəyir. Məsələn, əgər onun strategiyası $1/2$ ehtimalla $10$, $1/4$ ehtimalla $8$ və $1/4$ ehtimalla $0$ ödənişi qazandırırsa, onda gözlənilən ödənişi çəkili orta qiymət olan 10 \cdot (1/2) + 8 \cdot (1/4) + 0 \cdot (1/4) = 7-dir.