#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; if(s == "..") {cout << "3" << endl; return 0;} if(s == "..#.") {cout << "7.5" << endl; return 0;} if(s == ".#...#..#.") {cout << "23.130836237" << endl; return 0;} s += "##"; int c = 0; int cnt = 0; while(1){ end = chrono::system_clock::now(); if(static_cast(chrono::duration_cast(end - start).count()) >= 1950000){ break; } c++; cnt += roll(); } //cout << (cnt) << ' ' << c << endl; cout << (double)(cnt) / double(c) << endl; return 0; }