#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; class myDeque { private: deque > dq; double offset; public: myDeque(){ offset = 0.0; } void push_front(pair a){ a.first -= offset; dq.push_front(a); } void push_back(pair a){ a.first -= offset; dq.push_back(a); } pair front(){ auto a = dq.front(); a.first += offset; return a; } pair back(){ auto a = dq.back(); a.first += offset; return a; } void pop_front(){ dq.pop_front(); } void pop_back(){ dq.pop_back(); } bool empty(){ return dq.empty(); } void addAll(double x){ offset += x; } }; bool check(const vector& a, int k) { int n = a.size(); double sum = 0.0; myDeque dq; for(int i=k; i= 0.0) return true; val -= a[i]; val += a[(k+i)%n]; sum -= a[(k+i)%n]; sum += a[i]; dq.addAll(-a[(k+i)%n]); if(dq.front().second == (k+i)%n) dq.pop_front(); while(!dq.empty() && dq.back().first < sum) dq.pop_back(); dq.push_back(make_pair(sum, i)); } return false; } double solve(const string& s, int k) { int n = s.size(); double left = 0.0; double right = 1.0; for(int t=0; t<30; ++t){ double mid = (left + right) / 2.0; vector a(n); for(int i=0; i> n >> k >> s; double ans = solve(s, k); printf("%.10f\n", ans); return 0; }