問題一覧 > 通常問題

No.608 God's Maze

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 29
作問者 : hirakich1048576
お気に入りにしたユーザー ProblemId : 2038 / 自分の提出
問題文最終更新日: 2026-06-25 07:52:15
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2017 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。