#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 long double INF = LDBL_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 main(){ int K;cin>>K; Matrix A(K,Array(K,0)); repeat(i,K){ A[i][i] = 1; repeat(j,6){ int jj= i+1+j; if(jj==K)continue; if(jj>K)jj=0; A[i][jj] -= 1./6; } } Array B(K,1); Array ans = LU_backsubstitution(LU_decomposition(A),B); cout << ans[0] << endl; return 0; }