Так Ви хочете стати 2^n-ером?#1577

Так Ви хочете стати 2^n-ером? (Розбір)

Нехай $f (n, a)$ f(n, a) — максимально можливе значення очікуваного виграшу, якщо гравцю належить відповісти на $n$ питань, а початкова сума дорівнює $a$ .

Якщо $n = 0$ n = 0, гравець залишається з початковою сумою, тобто $f (0, a) = a$ f(0, a) = a.

Ймовірність правильної відповіді дорівнює $p$ , де $t \leq p \leq 1$ t \le p \le 1. Якщо гравець відповідає правильно на перше питання, йому залишається $n - 1$ n - 1 питань, а призова сума подвоюється і стає рівною $2 a$ . З ймовірністю $1 - p$ 1 - p дається неправильна відповідь, і вся сума пропадає. Отже, очікуваний виграш після першого питання дорівнює

p \cdot f (n - 1, 2 a) + (1 - p) \cdot 0 = p \cdot f (n - 1, 2 a)

p \cdot f(n - 1, 2a) + (1 - p) \cdot 0 = p \cdot f(n - 1, 2a)

Якщо це значення перевищує поточну суму $a$ , то вигідно продовжити гру; інакше — слід зупинитися. Таким чином, очікуваний виграш після рішення про продовження дорівнює

ma x (a, p \cdot f (n - 1, 2 a))

max(a, p \cdot f(n - 1, 2a))

Оскільки ймовірність $p$ рівномірно розподілена на відрізку $[t; 1]$ , то

f (n, a) = \frac{1}{1 - t} \int_{t}^{1} ma x (a, p \cdot f (n - 1, 2 a)) d p

f(n, a) = \frac{1}{1 - t} \int_{t}^{1} max(a, p \cdot f(n - 1, 2a))\,dp

Якщо $t = 1$ t = 1, то ймовірність правильної відповіді дорівнює одиниці, і тоді гравець повинен відповідати на всі $n$ питань, отримуючи підсумковий виграш $2^{n}$ 2^n.

Приклад

Розглянемо третій тест, у якому $n = 2, t = 0.6$ n = 2, t = 0.6. Початковий капітал $a = 1$ a = 1.

f (2, 1) = \frac{1}{0.4} \int_{0.6}^{1} ma x (1, p \cdot f (1, 2)) d p, f (1, 2) = \frac{1}{0.4} \int_{0.6}^{1} ma x (2, p \cdot f (0, 4)) d p, f (0, 4) = 4

f(2, 1) = \frac{1}{0.4} \int_{0.6}^{1} max(1, p \cdot f(1, 2))~dp, \\ f(1, 2) = \frac{1}{0.4} \int_{0.6}^{1} max(2, p \cdot f(0, 4))~dp, \\ f(0, 4) = 4

Обчислимо значення $f (1, 2)$ f(1, 2) через $f (0, 4)$ f(0, 4):

f (1, 2) = \frac{1}{0.4} \int_{0.6}^{1} ma x (2, p \cdot f (0, 4)) d p = 2.5 \cdot \int_{0.6}^{1} ma x (2, 4 p) d p = / враховуємо, що 4 p > 2 при 0.6 \leq p \leq 1/ 2.5 \cdot \int_{0.6}^{1} 4 p d p = 2.5 \cdot [2 p^{2}]_{0.6}^{1} = 5 \cdot (1 - 0.36) = 5 \cdot 0.64 = 3.2

f(1, 2) = \frac{1}{0.4} \int_{0.6}^{1} max(2, p \cdot f(0, 4))~dp = 2.5 \cdot \int_{0.6}^{1} max(2, 4p)~dp = \\ / враховуємо, що~4p > 2~при~0.6 \le p \le 1 / \\ 2.5 \cdot \int_{0.6}^{1} 4p~dp = 2.5 \cdot \left[ 2 p^2 \right]_{0.6}^{1} = \\ 5 \cdot (1 - 0.36) = 5 \cdot 0.64 = 3.2

Обчислимо значення $f (2, 1)$ f(2, 1) через $f (1, 2)$ f(1, 2):

f (2, 1) = \frac{1}{0.4} \int_{0.6}^{1} ma x (1, p \cdot f (1, 2)) d p = 2.5 \cdot \int_{0.6}^{1} ma x (1, 3.2 p) d p = / враховуємо, що 3.2 p > 1 при 0.6 \leq p \leq 1/ 2.5 \cdot \int_{0.6}^{1} 3.2 p d p = 2.5 \cdot [1.6 p^{2}]_{0.6}^{1} = 4 \cdot (1 - 0.36) = 4 \cdot 0.64 = 2.56

f(2, 1) = \frac{1}{0.4} \int_{0.6}^{1} max(1, p \cdot f(1, 2))~dp = 2.5 \cdot \int_{0.6}^{1} max(1, 3.2p)~dp = \\ / враховуємо, що~3.2p > 1~при~0.6 \le p \le 1 / \\ 2.5 \cdot \int_{0.6}^{1} 3.2p~dp = 2.5 \cdot \left[ 1.6 p^2 \right]_{0.6}^{1} = \\ 4 \cdot (1 - 0.36) = 4 \cdot 0.64 = 2.56

Реалізація алгоритму

Функція integral обчислює значення інтеграла

I (a, k) = \frac{1}{1 - t} \int_{t}^{1} ma x (a, k p) d p

I(a, k) = \frac{1}{1 - t} \int_{t}^{1} max(a, kp)\,dp

для заданих дійсних чисел $a$ і $k$ . При $t = 1$ t = 1 ймовірність вгадування $p$ дорівнює одиниці, тому значення інтеграла $I (a, k)$ I(a, k) покладається рівним $ma x (a, k)$ max(a, k).

Нижче показана область, площа якої дорівнює значенню інтеграла $\int_{t}^{1} ma x (a, k p) d p$ \int_{t}^{1} max(a, kp)\,dp:

Знайдемо точку перетину прямих $y = a$ y = a і $y = k p$ y = kp:

a = k p, звідки p = a / k

a = kp,~ звідки~p = a/k

Покладемо $t e m p = a / k$ temp = a / k. Значення інтеграла $\int_{t}^{1} ma x (a, k p) d p$ \int_{t}^{1} max(a, kp)\,dp розглянемо як суму $\int_{t}^{t e m p} a d p$ \int_{t}^{temp} a\,dp + $\int_{t e m p}^{1} k p d p$ \int_{temp}^{1} kp\,dp. Залежно від положення точки $t e m p$ відносно точок $t$ та $1$ обчислюємо значення інтеграла $I (a, k)$ I(a, k).

Якщо $t \leq t e m p \leq 1$ t \le temp \le 1, то $\int_{t}^{t e m p} a d p$ \int_{t}^{temp} a\,dp + $\int_{t e m p}^{1} k p d p$ \int_{temp}^{1} kp\,dp =

a \cdot (t e m p - t) + k \cdot (1 - t e m p \cdot t e m p) /2

a \cdot (temp - t) + k \cdot (1 - temp \cdot temp) / 2

Якщо $t e m p \leq t$ temp \le t, то $\int_{t}^{t e m p} a d p$ \int_{t}^{temp} a\,dp + $\int_{t e m p}^{1} k p d p$ \int_{temp}^{1} kp\,dp = $\int_{t}^{1} k p d p$ \int_{t}^{1} kp\,dp = $k \cdot (1 - t \cdot t) /2$ k \cdot (1 - t \cdot t) / 2.
Якщо $t e m p > 1$ temp > 1, то $\int_{t}^{t e m p} a d p$ \int_{t}^{temp} a\,dp + $\int_{t e m p}^{1} k p d p$ \int_{temp}^{1} kp\,dp = $\int_{t}^{1} a d p$ \int_{t}^{1} a\,dp = $a \cdot (1 - t)$ a \cdot (1 - t).

double integral(double a, double k)
{
  double s = 0, temp = a / k;
  if (t == 1) return max(a,k);
  if (temp > 1) return a * (1 - t);
  if (temp >= t) s = a * (temp - t);
  else temp = t;
  s += k * (1 – temp * temp) / 2;
  return s / (1 - t);
}

C++

Функція f рекурсивно обчислює значення $f (n, a) = {I (a, f (n - 1, 2 a)), n > 0 a, n = 0$ f(n, a) = \begin{cases} I(a, f(n - 1, 2a)), n > 0 \\ a, n = 0 \end{cases}.

double f(int n, int a)
{
  if (!n) return a;
  double k = f(n - 1,2 * a);
  return integral(a,k);
}

Основний цикл програми. Читаємо вхідні дані та виводимо значення $f (n, 1)$ f(n, 1).

while(scanf("%d %lf",&n,&t),n + t)
  printf("%.3lf\n",f(n,1));