Kasib Miku#12214

Kasib Miku (Həll təhlili)

Problem Müəllifi:	De3b0o
Hazırlayan:	De3b0o
Redaktə edən:	De3b0o

Həll

$E (l, j)$ E(l,j)-ni Miku-nun $l$ qatında $j$ slotuna topu atdıqda alacağı gözlənilən pul sayısı kimi müəyyən edək.

$(l, j)$ (l,j)-dən top:

sola $(l + 1, j)$ (l+1,j)-yə $\frac{1}{2}$ \frac{1}{2} ehtimalı ilə gedir.
sağa $(l + 1, j + 1)$ (l+1,j+1)-yə $\frac{1}{2}$ \frac{1}{2} ehtimalı ilə gedir.

Beləliklə:

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

Yuxarıdakı tənlikdən görürük ki, aşağıdakı iki şərtdən ən az biri doğrudur:

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

Çünki əgər hər ikisi yanlış olsaydı, onda $E (l + 1, j) + E (l + 1, j + 1)$ E(l+1,j) + E(l+1,j+1) $E (l, j)$ E(l,j)-dən qat-qat az olardı və bərabər olmazdı.

Beləliklə, topu ( $n - 1$ n-1)-ci qatda atmağın həmişə optimal olduğunu nəticəsinə gəlirik.

Aşağıda $O (n)$ implementasiyası verilmişdir.

#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';
    }
}