No.608 God's Maze
タグ : / 解いたユーザー数 29
作問者 :
hirakich1048576
Problem Statement
Ib is a dead soul who has fallen into Hell. Today, as a penance, Ib has been put in a tower, and must solve the puzzle on the floor in order to get out.
On the floor, $ |S| $ unlit tiles are arranged in a horizontal row, and Ib is initially on the $ N $-th tile from the left.
From there, Ib can move left or right, one cell at a time. However, Ib cannot step off the tiles.
Each time Ib moves one cell, the tile Ib stepped on toggles between lit and unlit. Note that the tile Ib was initially on is unlit at the time the movement begins.
A string $ S $ is given to Ib in advance. The goal of the puzzle is to make the $ i $-th tile from the left unlit if $ S_i $ is $ \mathtt{'.'} $, and lit if it is $ \mathtt{'\#'} $.
As God, you have decided to help Ib escape. Since Ib has been climbing the tower for several days without sleep or food, Ib wants to solve the puzzle with as few moves as possible.
Find the minimum number of moves in a procedure that clears the puzzle.
Input
N S
The first line contains an integer $N$($ 1 \leqq N \leqq |S| $).
The second line contains a string $S$($ 2 \leqq |S| \leqq 100000 $).
$S$ consists of the characters $ \mathtt{'.'} $ and $ \mathtt{'\#'} $, and contains at least one $ \mathtt{'\#'} $.
Output
Output the minimum number of moves in a procedure that clears the puzzle. Do not forget the newline at the end.
Sample
Sample 1
Input
4 #..##
Output
7
Ib's initial position is on the 4th tile from the left.
From there, moving 3 cells left gives the state $ \mathtt{\#\#\#..} $, and then moving 4 cells right gives the state $ \mathtt{\#..\#\#} $.
Sample 2
Input
3 #####
Output
11
Sample 3
Input
4 ###..#....#.#
Output
24
Sample 4
Input
12 #.####....###.#
Output
35
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。