Бідна Міку#12214

Бідна Міку (Розбір)

Автор проблеми:	De3b0o
Підготовлено:	De3b0o
Редаговано:	De3b0o

Рішення

Позначимо $E (l, j)$ E(l,j) як очікувану кількість монет, які Міку отримає, якщо вона скине м'яч у шарі $l$ , слот $j$ .

З $(l, j)$ (l,j) м'яч йде:

вліво до $(l + 1, j)$ (l+1,j) з ймовірністю $\frac{1}{2}$ \frac{1}{2}.
вправо до $(l + 1, j + 1)$ (l+1,j+1) з ймовірністю $\frac{1}{2}$ \frac{1}{2}.

Отже:

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

З наведене рівняння ми можемо побачити, що принаймні одна з двох наступних умов є істинною:

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

Бо якщо б обидві були неправильними, тоді $E (l + 1, j) + E (l + 1, j + 1)$ E(l+1,j) + E(l+1,j+1) було б строго менше ніж $E (l, j)$ E(l,j) і не дорівнювало б.

Отже, ми приходимо до висновку, що завжди оптимально скидати м'яч на ( $n - 1$ n-1)-му шарі.

Наступне є реалізацією з складністю $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';
    }
}