#include #include #include #include #include #include #include #include #include #include #include #include #include #define repeat(i,n) for (int i = 0; (i) < int(n); ++(i)) #define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i)) #define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i)) #define repeat_from_reverse(i,m,n) for (int i = (n)-1; (i) >= int(m); --(i)) #define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x) typedef long long ll; using namespace std; template void setmax(T & a, T const & b) { if (a < b) a = b; } template void setmin(T & a, T const & b) { if (b < a) a = b; } template auto vectors(X x, T a) { return vector(x, a); } template auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector(x, cont); } using real = double; const real eps = 1e-14; vector > operator * (vector > const & p, vector > const & q) { int n = p.size(); vector > r(n, vector(n)); repeat (y,n) repeat (z,n) repeat (x,n) r[y][x] += p[y][z] * q[z][x]; return r; } vector operator * (vector > const & p, vector const & q) { int n = p.size(); vector r(n); repeat (y,n) repeat (z,n) r[y] += p[y][z] * q[z]; return r; } vector > unit_matrix(int n) { vector > e(n, vector(n)); repeat (i,n) e[i][i] = 1; return e; } vector > zero_matrix(int n) { vector > o(n, vector(n)); return o; } vector gaussian_elimination(vector > f, vector x) { int n = x.size(); repeat (y,n) { int pivot = y; while (pivot < n and abs(f[pivot][y]) < eps) ++ pivot; assert (pivot < n); swap(f[y], f[pivot]); x[y] /= f[y][y]; repeat_from (x,y+1,n) f[y][x] /= f[y][y]; f[y][y] = 1; repeat (ny,n) if (ny != y) { x[ny] -= f[ny][y] * x[y]; repeat_from (x,y+1,n) f[ny][x] -= f[ny][y] * f[y][x]; f[ny][y] = 0; } } return x; } int main() { int n, m; scanf("%d%d", &n, &m); vector c(n); repeat (i,n-2) scanf("%d", &c[i+1]); vector init; { vector > f = vectors(m-1, m-1, real()); vector v = vectors(m-1, real()); repeat (y,m-1) { f[y][y] += m; repeat (x,m) { int z = min(y+x+1, 2*(m-1)-(y+x+1)); if (z == m-1) continue; f[y][z] -= 1; v[y] += c[n-m+z]; } } // repeat (y,m-1) { repeat (x,m-1) { cerr << f[y][x] << ' '; } cerr << " : " << v[y]<< endl; } init = gaussian_elimination(f, v); // cerr << "-> "; repeat (y,m-1) cerr << init[y] << ' ' ; cerr << endl; } vector dp1(n); repeat_reverse (i,n) { if (i == n-1) { // zero } else if (n-m <= i) { dp1[i] = init[i-(n-m)]; } else { repeat (j,m) dp1[i] += (c[i+j+1] + dp1[i+j+1]) / m; } } vector dp0(n); repeat_reverse (i,n) { if (n-m-1 <= i) { // zero } else { repeat (j,m) dp0[i] += (c[i+j+1] + dp0[i+j+1]) / m; repeat (j,m) setmin(dp0[i], c[i+j+1] + dp1[i+j+1]); } } // repeat (i,n) cerr << dp1[i] << ' '; cerr << endl; // repeat (i,n) cerr << dp0[i] << ' '; cerr << endl; printf("%.12lf\n", dp0[0]); return 0; }