#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; typedef double number; const number eps = 1e-10; typedef vector arr; typedef vector matrix; // O( n ) matrix identity(int n) { matrix A(n, arr(n)); for (int i = 0; i < n; ++i) A[i][i] = 1; return A; } // O( n ) number inner_product(const arr &a, const arr &b) { number ans = 0; for (int i = 0; i < a.size(); ++i) ans += a[i] * b[i]; return ans; } // O( n^2 ) arr mul(const matrix &A, const arr &x) { arr y(A.size()); for (int i = 0; i < A.size(); ++i) for (int j = 0; j < A[0].size(); ++j) y[i] = A[i][j] * x[j]; return y; } // O( n^3 ) matrix mul(const matrix &A, const matrix &B) { matrix C(A.size(), arr(B[0].size())); for (int i = 0; i < C.size(); ++i) for (int j = 0; j < C[i].size(); ++j) for (int k = 0; k < A[i].size(); ++k) C[i][j] += A[i][k] * B[k][j]; return C; } // O( n^3 log e ) matrix pow(const matrix &A, int e) { return e == 0 ? identity(A.size()) : e % 2 == 0 ? pow(mul(A, A), e/2) : mul(A, pow(A, e-1)); } // O( n^3 ) number det(matrix A) { const int n = A.size(); number D = 1; 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]); D *= A[i][i] * (i != pivot ? -1 : 1); if (abs(A[i][i]) < eps) break; for(int j = i+1; j < n; ++j) for(int k = n-1; k >= i; --k) A[j][k] -= A[i][k] * A[j][i] / A[i][i]; } return D; } // O(n) number tr(const matrix &A) { number ans = 0; for (int i = 0; i < A.size(); ++i) ans += A[i][i]; return ans; } // O( n^3 ). int rank(matrix A) { const int n = A.size(), m = A[0].size(); int r = 0; for (int i = 0; r < n && i < m; ++i) { int pivot = r; for (int j = r+1; j < n; ++j) if (abs(A[j][i]) > abs(A[pivot][i])) pivot = j; swap(A[pivot], A[r]); if (abs(A[r][i]) < eps) continue; for (int k = m-1; k >= i; --k) A[r][k] /= A[r][i]; for(int j = r+1; j < n; ++j) for(int k = i; k < m; ++k) A[j][k] -= A[r][k] * A[j][i]; ++r; } return r; } 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 arr LU_backsubstitution(const LUinfo &data, arr 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 main() { int n, m; cin>>n>>m; double c[101]={}; for(int i=1; i>c[i]; } matrix a(n-1, arr(n-1)); arr b(n-1); for(int i=0; i=0; i--){ dp[i]=0; for(int j=1; j<=m; j++) dp[i]+=(dp[i+j]+c[i+j])/m; for(int j=1; j<=m; j++){ dp[i]=min(dp[i], sol[i+j]+c[i+j]); } } printf("%.10lf\n", dp[0]); return 0; }