Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 300 点
問題文
高橋君はペンギンのレース場を作りました。
レース場は N 個の正方形のマスが西から東に一列に並んだ形状をしています。
これらのマスの状態は文字列 S により表され、西から i 番目のマスの状態は S の i 文字目が -
なら「雪」、>
なら「氷」です。
また、スタート地点は西端のマスの西の端、ゴール地点は東端のマスの東の端です。
高橋くんのペンギンが、スタート地点からゴール地点を目指して東に進みます。
ペンギンは、雪マスを 1 マス通過するのに 1 秒、氷マスを 1 マス通過するのに 1/(k+2) 秒の時間を要します。
ここで、k はその氷マスの直前に連続して存在する氷マスの個数です。
例えば、雪マスの直後に氷マスが 2 つ存在する場合、1 つ目の氷マスは 1/2 秒、2 つ目の氷マスは 1/3 秒で通過します。
ペンギンがスタートする前に、高橋君は雪マスのうち 1 つを氷マスに変えることができます。
ペンギンがスタート地点を出発してからゴール地点に到達するまでに最小で何秒かかるでしょうか?
制約
- 3 \leq N \leq 100 \ 000
- S は
-
,>
で構成される長さ N の文字列 - S_1 = S_2 = S_{N-1} = S_N =
-
- S において、
-
は必ず別の-
と隣接して現れる
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
ペンギンがゴール地点に到達するのに要する秒数の最小値を出力せよ。
ジャッジの出力との相対誤差または絶対誤差が 10^{-8} 以下であれば正解となる。
入力例 1
5 -->--
出力例 1
3.83333333333333
西から 4 番目のマスを雪マスから氷マスに変えると、レース場は -->>-
となります。
このとき、ペンギンは西から 1, 2, 3, 4, 5 番目のマスの通過にそれぞれ 1, 1, 1/2, 1/3, 1 秒、合計で 23/6 = 3.83333333... 秒を要し、これが最短です。
入力例 2
7 -------
出力例 2
6.5
どのマスを雪マスから氷マスに変えても、ペンギンは 13/2 = 6.5 秒でゴールします。
入力例 3
10 -->>>-->--
出力例 3
6.78333333333333
西から 2 番目または 6 番目のマスを雪マスから氷マスに変えると、ペンギンは 407/60 = 6.783333333... 秒でゴールすることができます。