Pauvre Miku#12214

Pauvre Miku (Corrigé)

Auteur du problème:	De3b0o
Préparé par:	De3b0o
Édité par:	De3b0o

Solution

Définissons $E (l, j)$ E(l,j) comme le nombre attendu de pièces que Miku obtiendra si elle laisse tomber la balle à la couche $l$ emplacement $j$ .

Depuis $(l, j)$ (l,j), la balle va :

à gauche vers $(l + 1, j)$ (l+1,j) avec une probabilité de $\frac{1}{2}$ \frac{1}{2}.
à droite vers $(l + 1, j + 1)$ (l+1,j+1) avec une probabilité de $\frac{1}{2}$ \frac{1}{2}.

Donc :

$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)

D'après l'équation ci-dessus, nous pouvons voir qu'au moins une des deux conditions suivantes est vraie :

$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).

Parce que si les deux étaient fausses, alors $E (l + 1, j) + E (l + 1, j + 1)$ E(l+1,j) + E(l+1,j+1) serait strictement inférieur à $E (l, j)$ E(l,j) et non égal.

Nous arrivons donc à la conclusion qu'il est toujours optimal de laisser tomber la balle à la couche ( $n - 1$ n-1).

Ce qui suit est une implémentation en $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 << "OUI" << "\n";
#define no cout << "NON" << "\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';
    }
}