問題一覧 > 通常問題

No.608 God's Maze

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 30
作問者 : hirakich1048576hirakich1048576
2 ProblemId : 2038 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-12-08 00:52:43

問題文

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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。