## 1) Concise abridged problem statement

You must type a string of length `n`. Typing any key (including backspace) costs `1` time unit. Looking at the screen costs `t` time units.  
When you look at the screen, if there is at least one typo, you delete (via backspaces) from the end back to **and including** the first wrong character, leaving only the correct prefix, then continue typing from there.  
Character `i` is mistyped independently with probability `a[i]`.

Choose when to look at the screen to minimize the **expected** total time to finish typing correctly and finally verify (a last screen check that finds no typos). Output the minimum expected time.

Constraints: `n ≤ 3000`.

---

## 2) Detailed editorial (solution explanation)

### Key observation: decisions only matter at “known-correct prefix” moments
After you look at the screen and delete back to the first mistake, you end up with some prefix of length `k` that is guaranteed correct. From that state, the future depends only on `k`, not on how you got there.

So define:

- `dp[k]` = minimal expected remaining time to finish the whole text **given** that the first `k` characters are correct.
- Answer is `dp[0]`.
- Base: `dp[n] = 0` (nothing left to type, but note: the final verification must be included by the strategy; in our transitions we always include a screen check after typing a block, including the final one).

### Transition: type a block then look
From state `k`, choose to type the next `p` characters (so you type positions `k+1 ... k+p`, where `1 ≤ p ≤ n-k`), then look at the screen.

Immediate deterministic cost:
- typing `p` keys: `p`
- looking at screen: `t`
Total so far: `p + t`

Now outcomes after the screen check:

Let `q_j = P(first j typed characters are all correct)` for this block.
- `q_0 = 1`
- `q_j = ∏_{i=1..j} (1 - a[k+i])`

If there is a mistake, you backspace to the first mistake (inclusive).  
If the first mistake is at relative position `j` (1-based in this block), then after the screen check you will:
- backspace exactly `p - (j-1)` characters (you remove from end down to `k+j`)
- and you return to state `k + (j-1)` (because first `k + (j-1)` are correct)

Probability that first mistake is exactly at `j`:
- `P = q_{j-1} * a[k+j]`

If there is no mistake in the block (`j = p+1` case), probability `q_p`, you move to state `k+p` with no backspaces.

So the expectation for choosing block size `p` is:

\[
E(k,p) = p + t \;+\; \sum_{j=1}^{p} \left(q_{j-1} a_{k+j}\right)\left((p-j+1) + dp[k+j-1]\right) \;+\; q_p \, dp[k+p].
\]

Then:
\[
dp[k] = \min_{p=1..n-k} E(k,p).
\]

### Making it efficient (O(n²), not O(n³))
Directly computing `E(k,p)` from scratch for each `p` would be too slow.

We iterate `p` from 1 upward and maintain cumulative sums:

Let `q` be current `q_p = ∏_{i=1..p} (1 - a[k+i])`.

For `j = 1..p-1` we need terms of the form:
- `q_{j-1} a[k+j]` (probability first mistake at j)
- multiplied by `(p-j+1)` and by `dp[k+j-1]`

Notice when `p` increases by 1, `(p-j+1)` increases by 1 for all previous `j`, so we can maintain:
- `c1 = Σ (q_{j-1} a[k+j])`
- `c2 = Σ (q_{j-1} a[k+j] * j)` or (as in code) `* p`-shifted variants
- `b  = Σ (q_{j-1} a[k+j] * dp[k+j-1])`

The provided solution uses a slightly re-indexed form (to avoid recomputing and to keep formulas clean), but the idea is the same: maintain running weighted sums of “first error at position j” probabilities and their contributions.

### Handling the cyclic-looking term
When you expand the expectation, there can appear a term involving `dp[k]` on both sides (because if the first typed char is wrong, you return to the same `k`). The trick is: that dependence is linear and can be moved to the left:

\[
dp[k] = X + a[k+1]\cdot dp[k] \Rightarrow dp[k] = \frac{X}{1-a[k+1]}.
\]

In the code, indexing is shifted (0-based), and it ends up dividing by `(1 - a[k])` due to how terms are arranged; the algebra is equivalent under their chosen reparameterization.

### Complexity
For each `k` (there are `n`), we scan `p = 1..n-k` and update O(1) accumulators. Total:

- Time: `O(n^2)` ≈ 9e6 operations for n=3000 (fits in 0.25s in optimized C++).
- Memory: `O(n)`.

---

## 3. C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
double t;
vector<double> a;

void read() {
    cin >> n >> t;
    a.resize(n);
    cin >> a;
}

void solve() {
    // When we see this problem a direct thought is to try doing DP. Let's have
    // the state dp[i] be the minimal expected time to complete this process if
    // we know that the first i characters are correct. Then the answer is
    // dp[0], and we know that dp[n] = 0. Let's say we know the first k
    // character are correct and try to calculate dp[k]. Let's try to fix the
    // next time q = k + p at which we will try to look at the screen to verify.
    // Overall, this would take p + t time, and then we also need to account the
    // time needed to actually press backspace. There is probability a[k + 1]
    // that we will fail at the first typed character, which will lead us back
    // to dp[k], and (1 - a[k + 1]) probability that this will succeed and we
    // would fail at one of the later ones. If we continue like this, we get
    // that:
    //
    //    dp[k] = min(dp[k],
    //                p + t +
    //                a[k + 1] * (dp[k] + p) +
    //                (1 - a[k + 1]) * a[k + 2] * (dp[k + 1] + p - 1) +
    //                     ...
    //                (1 - a[k + 1]) * ... * (1 - a[p]) * dp[k])
    //
    // And this minimized over all k + p <= n. Note that there is a cyclic term
    // in all of these p, where the common approach when we don't optimize and
    // just compute expectation is to move it on the other side of the equation.
    // Turns out that this term depending on dp[k] is always the same! This
    // means that we can subtract both sides by a[k + 1] * dp[k], making the DP
    // a DAG. The only part left is to implement this efficiently. Naively
    // performing this minimum would be O(N^3) that is a bit too slow, but we
    // can notice that we can compute the p-th transition based on temporary
    // results based on the (p-1)th transition. This way we can also get a
    // quadratic complexity.

    vector<double> dp(n + 1, 0.0);

    for(int k = n - 1; k >= 0; k--) {
        dp[k] = 1e18;
        double q = 1.0;
        double c1 = 0.0, c2 = 0.0, b_val = 0.0;
        for(int p = 1; p <= n - k; p++) {
            q *= (1.0 - a[k + p - 1]);

            double g = p * (1.0 + a[k] + c1) - c2 + t + b_val + q * dp[k + p];
            dp[k] = min(dp[k], g / (1.0 - a[k]));
            if(p < n - k) {
                double term = q * a[k + p];
                c1 += term;
                c2 += term * p;
                b_val += term * dp[k + p];
            }
        }
    }

    cout << fixed << setprecision(15) << dp[0] << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 4) Python solution (same algorithm) with detailed comments

```python
import sys
import math

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    t = float(next(it))
    a = [float(next(it)) for _ in range(n)]

    # dp[k] = minimal expected remaining time given first k characters are correct
    dp = [0.0] * (n + 1)   # dp[n] = 0 base case

    # Compute backwards
    for k in range(n - 1, -1, -1):
        best = 1e100

        q = 1.0       # probability all typed-so-far in current block are correct
        c1 = 0.0      # accumulator (see C++ code / editorial)
        c2 = 0.0      # accumulator
        b_val = 0.0   # accumulator of dp contributions

        # try p = 1..(n-k) characters typed before looking
        for p in range(1, n - k + 1):
            # update q = Π_{i=0..p-1} (1 - a[k+i])
            q *= (1.0 - a[k + p - 1])

            # same rearranged expectation numerator as in the C++ solution
            g = (
                p * (1.0 + a[k] + c1)
                - c2
                + t
                + b_val
                + q * dp[k + p]
            )

            # rearranged division to remove the dp[k] term on RHS
            cand = g / (1.0 - a[k])
            if cand < best:
                best = cand

            # update accumulators for the next p (if there is a next char)
            if p < n - k:
                term = q * a[k + p]     # prob first p correct and next wrong
                c1 += term
                c2 += term * p
                b_val += term * dp[k + p]

        dp[k] = best

    # print with enough precision
    sys.stdout.write("{:.15f}\n".format(dp[0]))

if __name__ == "__main__":
    solve()
```

Notes:
- This Python version is `O(n^2)` like the C++ one, but Python may be slower for `n=3000` under a very tight 0.25s limit. It is algorithmically correct; performance depends on the judge.

---

## 5) Compressed editorial

Let `dp[k]` be the minimum expected remaining time given the first `k` characters are surely correct (`dp[n]=0`). From state `k`, choose `p` characters to type, then pay `p+t` and look. The first mistake in that block occurs at some position with probability `q_{j-1} a[k+j]` (where `q` is the product of success probabilities), causing `p-j+1` backspaces and переход to `dp[k+j-1]`; if no mistakes, go to `dp[k+p]` with probability `q_p`. This yields a linear expectation that includes a term returning to `dp[k]`; move it to the left to get `dp[k]=g/(1-a[...])`. Evaluate all `p` and take the min. Maintain running sums of `q*a*1`, `q*a*pos`, and `q*a*dp[...]` so each `p` updates in O(1). Total time `O(n^2)`, memory `O(n)`.