No.608 God's Maze

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 24
作問者 : hirakich1048576hirakich1048576

2 ProblemId : 2038 / 出題時の順位表

問題文

Ibは地獄に堕ちた亡者である.今日は苦行として塔に入れられており,出るためには床のパズルを解かなければならない.

床には消灯した$ |S| $枚のタイルが横一列に並んでおり,Ibははじめ左から$ N $マス目のタイルの上にいる.
Ibはここから左か右に1マスずつ移動できる.ただし,タイルの上から外れることは出来ない.
1マス移動する度に,Ibが踏んだタイルの点灯・消灯が入れ替わる.ただし,Ibがはじめにいたタイルは移動を始めた時点では消灯している.
あらかじめ文字列$ S $がIbに与えられる.パズルの目標は,左から$ i $マス目のタイルを,$ S_i $が$ \mathtt{'.'} $であれば消灯,$ \mathtt{'\#'} $であれば点灯している状態にすることである.
あなたは神様としてIbの脱出を手伝うことにした.Ibは数日間睡眠も食事もせずに塔を登っていたため,なるべく少ない移動回数でパズルを解きたい.
パズルをクリアできる手順の移動回数の最小値を答えよ.

入力

N
S

1行目に整数$N$($ 1 \leqq N \leqq |S| $)が,
2行目には文字列$S$($ 2 \leqq |S| \leqq 100000 $)が与えられる.
$S$は$ \mathtt{'.'} $ か $ \mathtt{'\#'} $のいずれかの文字から構成されており,少なくとも1文字は$ \mathtt{'\#'} $がある.

出力

パズルをクリアできる手順の移動回数の最小値を答えよ.最後の改行を忘れないこと.

サンプル

サンプル1
入力
4
#..##
出力
7

Ibの初期位置は左から4マス目のタイル上です.
ここから左に3マス移動して$ \mathtt{\#\#\#..} $の状態にし,さらに右に4マス移動することで$ \mathtt{\#..\#\#} $の状態となります.

サンプル2
入力
3
#####
出力
11

サンプル3
入力
4
###..#....#.#
出力
24

サンプル4
入力
12
#.####....###.#
出力
35

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。