#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i)) #define debug(x) cerr << #x << ": " << x << '\n' #define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << '\n' #define debugArrayP(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge].first<< " " << x[hoge].second << '\n' using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair Pii; typedef vector vint; typedef vector vll; const double INF = DBL_MAX; const ll MOD = 998244353; typedef double number; const number eps = 1e-8; typedef vector Array; typedef vector Matrix; struct LUinfo { vector value; vector index; }; // O( n^3 ), Gaussian forward elimination LUinfo LU_decomposition(Matrix A) { const int n = A.size(); LUinfo data; for (int i = 0; i < n; ++i) { int pivot = i; for (int j = i+1; j < n; ++j) if (abs(A[j][i]) > abs(A[pivot][i])) pivot = j; swap(A[pivot], A[i]); data.index.push_back(pivot); // if A[i][i] == 0, LU decomposition failed. for(int j = i+1; j < n; ++j) { A[j][i] /= A[i][i]; for(int k = i+1; k < n; ++k) A[j][k] -= A[i][k] * A[j][i]; data.value.push_back(A[j][i]); } } for(int i = n-1; i >= 0; --i) { for(int j = i+1; j < n; ++j) data.value.push_back(A[i][j]); data.value.push_back(A[i][i]); } return data; } // O( n^2 ) Gaussian backward substitution Array LU_backsubstitution(const LUinfo &data, Array b) { const int n = b.size(); int k = 0; for (int i = 0; i < n; ++i){ swap(b[data.index[i]], b[i]); for(int j = i+1; j < n; ++j) b[j] -= b[i] * data.value[k++]; } for (int i = n-1; i >= 0; --i) { for (int j = i+1; j < n; ++j) b[i] -= b[j] * data.value[k++]; b[i] /= data.value[k++]; } return b; } int n,m; double dp[110]; int main(){ cin >>n>>m;n--; Array c(n); repeat(i,n-1){ cin>>c[i+1]; } Matrix A(n,Array(n,0)); repeat(i,n){ A[i][i] = 1; repeat(j,m){ int jj=i+1+j; if(jj==n){ continue; } if(jj>n){ jj = n-(jj-n); } A[i][jj] -= 1./m; } } Array f = LU_backsubstitution(LU_decomposition(A),c); for(int i=n-1;i>=0;i--){ dp[i] = INF; if(i+m>=n){ dp[i] = c[i]; continue; } double ave = 0; repeat(j,m){ dp[i] = min(dp[i],f[i+1+j]); ave += dp[i+1+j]; } ave /= m; dp[i] = min(dp[i],ave); dp[i] += c[i]; } printf("%lf\n",dp[0]); return 0; }