Quindi vuoi diventare un 2^n-ario?#1577

Quindi vuoi diventare un 2^n-ario? (Editoriale)

Sia $f (n, a)$ f(n, a) — il massimo valore possibile della vincita attesa, se il giocatore deve rispondere a $n$ domande e la somma iniziale è pari ad $a$ .

Se $n = 0$ n = 0, il giocatore resta con la somma iniziale, cioè $f (0, a) = a$ f(0, a) = a.

La probabilità di rispondere correttamente è pari a $p$ , dove $t \leq p \leq 1$ t \le p \le 1. Se il giocatore risponde correttamente alla prima domanda, gli restano $n - 1$ n - 1 domande, e la somma del premio raddoppia diventando $2 a$ . Con probabilità $1 - p$ 1 - p viene data una risposta errata, e l'intera somma va perduta. Di conseguenza, la vincita attesa dopo la prima domanda è pari a

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)

Se questo valore supera la somma attuale $a$ , allora è conveniente continuare il gioco; altrimenti — bisogna fermarsi. Quindi, la vincita attesa dopo la decisione di continuare è pari a

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

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

Poiché la probabilità $p$ è distribuita uniformemente sull'intervallo $[t; 1]$ , allora

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

Se $t = 1$ t = 1, allora la probabilità di rispondere correttamente è pari a uno, e in tal caso il giocatore deve rispondere a tutte le $n$ domande, ottenendo una vincita finale pari a $2^{n}$ 2^n.

Esempio

Consideriamo il terzo test, in cui $n = 2, t = 0.6$ n = 2, t = 0.6. Il capitale iniziale è $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

Calcoliamo il valore di $f (1, 2)$ f(1, 2) tramite $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 = / t e niam oco n t oc h e 4 p > 2 p er 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 = \\ / teniamo conto che~4p > 2~per~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

Calcoliamo il valore di $f (2, 1)$ f(2, 1) tramite $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 = / t e niam oco n t oc h e 3.2 p > 1 p er 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 = \\ / teniamo conto che~3.2p > 1~per~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

Implementazione dell'algoritmo

La funzione integral calcola il valore dell'integrale

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

per i numeri reali dati $a$ e $k$ . Quando $t = 1$ t = 1, la probabilità di indovinare $p$ è pari a uno, quindi il valore dell'integrale $I (a, k)$ I(a, k) viene posto uguale a $ma x (a, k)$ max(a, k).

Di seguito è mostrata l'area la cui superficie è pari al valore dell'integrale $\int_{t}^{1} ma x (a, k p) d p$ \int_{t}^{1} max(a, kp)\,dp:

Troviamo il punto di intersezione delle rette $y = a$ y = a e $y = k p$ y = kp:

a = k p, d a c u i p = a / k

a = kp,~ da cui~p = a/k

Poniamo $t e m p = a / k$ temp = a / k. Consideriamo il valore dell'integrale $\int_{t}^{1} ma x (a, k p) d p$ \int_{t}^{1} max(a, kp)\,dp come somma di $\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 seconda della posizione del punto $t e m p$ rispetto ai punti $t$ e $1$ , calcoliamo il valore dell'integrale $I (a, k)$ I(a, k).

Se $t \leq t e m p \leq 1$ t \le temp \le 1, allora $\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

Se $t e m p \leq t$ temp \le t, allora $\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.
Se $t e m p > 1$ temp > 1, allora $\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++

La funzione f calcola ricorsivamente il valore $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);
}

Ciclo principale del programma. Leggiamo i dati in ingresso e stampiamo il valore di $f (n, 1)$ f(n, 1).

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