/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 475 点
問題文
o と x からなる長さ N の文字列 S が与えられます。
ただし、S には o が K 個以上含まれることが保証されます。
高橋君はあるゲームを N 回行いました。
i 回目のゲームでは、S の i 文字目が o ならば高橋君は勝利し、x ならば高橋君は敗北しました。
高橋君は以下の条件を満たすような 2 整数 l,r を一つ選びます。
- 1 \leq l \leq r \leq N
- l 回目から r 回目までのゲームで K 勝以上している
このとき、l 回目から r 回目までのゲームでの勝率としてあり得る値の最大値を求めてください。
制約
- 1 \leq K \leq N \leq 10^6
- N と K は整数
- S は
oとxからなる長さ N の文字列 - S は
oを K 個以上含む
入力
入力は以下の形式で標準入力から与えられる。
N K S
出力
答えを 1 行で出力せよ。 真の答えとの絶対誤差または相対誤差が 10^{-6} 以下であれば正解として扱われる。
入力例 1
10 4 oxooxoxxox
出力例 1
0.6666666666
(l,r) として (1,6) を選ぶと勝率は \frac{2}{3} です。
条件を満たす範囲で勝率をこれより大きくすることはできません。
入力例 2
5 1 xxoxx
出力例 2
1
入力例 3
16 10 xxxoxooooxoxoooo
出力例 3
0.769230769230769
Score : 475 points
Problem Statement
You are given a string S of length N consisting of o and x.
It is guaranteed that S contains at least K occurrences of o.
Takahashi played a certain game N times.
In the i-th game, he won if the i-th character of S is o, and lost if it is x.
Takahashi chooses a pair of integers l and r satisfying the following conditions.
- 1 \leq l \leq r \leq N
- He won at least K times in the games from the l-th through the r-th.
Find the maximum possible value of the win rate in the games from the l-th through the r-th.
Constraints
- 1 \leq K \leq N \leq 10^6
- N and K are integers.
- S is a string of length N consisting of
oandx. - S contains at least K occurrences of
o.
Input
The input is given from Standard Input in the following format:
N K S
Output
Output the answer in one line. Answers with an absolute or relative error of at most 10^{-6} from the true answer will be accepted.
Sample Input 1
10 4 oxooxoxxox
Sample Output 1
0.6666666666
Choosing (1,6) as (l,r) gives a win rate of \frac{2}{3}.
It is impossible to make the win rate larger than this while satisfying the conditions.
Sample Input 2
5 1 xxoxx
Sample Output 2
1
Sample Input 3
16 10 xxxoxooooxoxoooo
Sample Output 3
0.769230769230769