#include #include #include #include #include using namespace std; int n, m; vector c; int main() { cin >> n >> m; c = vector(n); for(int i = 1; i < n - 1; i++) { cin >> c[i]; } // 後ろからの期待値 // x_i マス iに居る時の期待値 vector> M(n, vector(n + 1)); // x_n = 0 M[n-1][n-1] = 1; M[n-1][n] = 0; for(int i = 0; i < n - 1; i++) { for(int j = 1; j <= m; j++) { int to = i + j; if(to >= n) to = n - (to - n) - 1; M[i][to] = -1.0 / m; } M[i][i] = 1; M[i][n] = c[i]; } // for(int i = 0; i < n; i++) { // for(int j = 0; j <= n; j++) { // cout // << M[i][j] << " "; // } // cout << endl; // } for(int i = 0; i < n; i++) { int pivot = i; for(int j = i; j < n; j++) { if(fabs(M[j][i]) > fabs(M[pivot][i])) pivot = j; } swap(M[pivot], M[i]); for(int j = i + 1; j <= n; j++) { M[i][j] /= M[i][i]; } M[i][i] = 1; for(int j = 0; j < n; j++) { if(i == j) continue; double div = M[j][i] / M[i][i]; for(int k = 0; k <= n; k++) { M[j][k] -= div * M[i][k]; } } } vector de(n), dp(n); for(int i = 0; i < n; i++) de[i] = M[i][n]; for(int i = n - 1; i >= 0; i--) { if(i + m >= n - 1) dp[i] = min(de[i], c[i]); else { double t1 = 0; for(int j = 1; j <= m; j++) { t1 += dp[j + i]; } dp[i] = min(de[i], t1 / m + c[i]); for(int j = 1; j <= m; j++) { // dp[i] = min(dp[i], c[i] + de[i + j]); } } } cout << fixed << setprecision(10) << dp[0] << endl; // for(int i = 0; i < n; i++) { // cout << dp[i] << "," << de[i] << endl; // } }