Poor Miku#12214

Poor Miku (Editorial)

Problem Author:	De3b0o
Prepared by:	De3b0o
Edited by:	De3b0o

Solution

Let's define $E (l, j)$ E(l,j) as the expected number of coins Miku will get if she drops the ball at layer $l$ slot $j$ .

From $(l, j)$ (l,j), the ball goes:

left to $(l + 1, j)$ (l+1,j) with probability $\frac{1}{2}$ \frac{1}{2}.
right to $(l + 1, j + 1)$ (l+1,j+1) with probability $\frac{1}{2}$ \frac{1}{2}.

So:

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

From the above equation, we can see that at least one of the two following conditions is true:

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

Because if they were both wrong then $E (l + 1, j) + E (l + 1, j + 1)$ E(l+1,j) + E(l+1,j+1) would be strictly less than $E (l, j)$ E(l,j) and not equal.

So we arrive to the conclusion that it's always optimal to drop the ball at the ( $n - 1$ n-1)-th layer.

The following is an $O (n)$ implementation.

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