#include #include using namespace std; using namespace atcoder; using mint = modint998244353; using ll = long long; #define all(x) x.begin(), x.end() #define rep(i, n) for (int i = 0; i < n; i++) string s; int n; int roll(){ std::random_device rnd; std::mt19937 mt(rnd()); int now = 0; int save = 0; int cnt = 0; int c; while(1){ c = mt() % 3; cnt++; if (c == 0){ now++; if (s[now] == '#') now = save; } if (c == 1){ now+=2; if (s[now] == '#') now = save; } if (c == 2) save = now; if (now == n - 1) return cnt; } } int main(void) { chrono::system_clock::time_point start, end; start = chrono::system_clock::now(); cin >> n; cin >> s; s += "##"; int c = 0; int cnt = 0; while(1){ end = chrono::system_clock::now(); if(static_cast(chrono::duration_cast(end - start).count() / 1000.0) >= 1900){ break; } c++; cnt += roll(); } cout << (double)cnt / c << endl; return 0; }