Pobre Miku#12214

Pobre Miku (Editorial)

Autor del problema:	De3b0o
Preparado por:	De3b0o
Editado por:	De3b0o

Solución

Definamos $E (l, j)$ E(l,j) como el número esperado de monedas que Miku obtendrá si deja caer la bola en la capa $l$ ranura $j$ .

Desde $(l, j)$ (l,j), la bola va:

a la izquierda a $(l + 1, j)$ (l+1,j) con probabilidad $\frac{1}{2}$ \frac{1}{2}.
a la derecha a $(l + 1, j + 1)$ (l+1,j+1) con probabilidad $\frac{1}{2}$ \frac{1}{2}.

Entonces:

$E (l, j) = \frac{1}{2} E (l + 1, j) + \frac{1}{2} E (l + 1, j + 1)$ E(l,j) = \frac{1}{2}E(l+1,j) + \frac{1}{2}E(l+1,j+1) $2 E (l, j) = E (l + 1, j) + E (l + 1, j + 1)$ 2E(l,j) = E(l+1,j) + E(l+1,j+1)

A partir de la ecuación anterior, podemos ver que al menos una de las dos siguientes condiciones es verdadera:

$E (l + 1, j) \geq E (l, j)$ E(l+1,j) \ge E(l,j).
$E (l + 1, j + 1) \geq E (l, j)$ E(l+1,j+1) \ge E(l,j).

Porque si ambas fueran falsas, entonces $E (l + 1, j) + E (l + 1, j + 1)$ E(l+1,j) + E(l+1,j+1) sería estrictamente menor que $E (l, j)$ E(l,j) y no igual.

Así que llegamos a la conclusión de que siempre es óptimo dejar caer la bola en la capa ( $n - 1$ n-1).

Lo siguiente es una implementación de $O (n)$ .

#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define mid ((l+r)/2)
#define lc (2*x)
#define rc (2*x+1)
#define double long double
 
using namespace std;

mt19937 rnd(time(0));

const ll N = 2e5+9;

double a[N];
double tw=2;

int main()
{
    d3
    ll T;
    cin >> T;
    while(T--)
    {
        ll n;
        cin >> n;
        for(int i = 1 ; n>=i ; i++)
            cin >> a[i];
        double mx = 0;
        for(int i = 1 ; n>i ; i++)
            mx=max(mx,a[i]+a[i+1]);
        mx/=tw;
        cout << fixed << setprecision(18) << mx << '\n';
    }
}