No.2035 Tunnel
タグ : / 解いたユーザー数 135
作問者 :
milkcoffee
/ テスター :
nok0
riano
Problem Statement
There are $N$ squares arranged in a straight line. The squares are numbered from $1$ to $N$, and each square holds at most $1$ piece.
The initial state of the squares is given by a string $S$: $S_i=$ # means that square $i$ has $1$ piece, and $S_i=$ . means that square $i$ is empty.
It is guaranteed that there exists at least $1$ square with a piece on it.
You want to remove all the pieces from the squares by repeatedly using magic.
Each $1$ use of the magic moves the pieces on the squares simultaneously according to the following rules.
- The piece on square $N$ is removed.
- A piece on square $i$ ($1 \leq i \leq N-1$) moves to square $(i+1)$ only if square $(i+1)$ has no piece immediately before the magic is used. Otherwise, it does not move.
Input
$N$ $S$
- $1 \leq N \leq 3 \times 10^5$
- $N$ is an integer.
- $S$ is a string of length $N$ consisting of
#and.. - $S$ contains at least $1$
#.
Output
Output, as an integer, the number of uses of the magic after which all the pieces are removed.
Sample
Sample 1
Input
3 ##.
Output
4
##. (initial): Square $1$ and square $2$ each have $1$ piece.
#.# (use $1$): The piece on square $2$ moves to square $3$. The piece on square $1$ does not move.
.#. (use $2$): The piece on square $3$ is removed. The piece on square $1$ moves to square $2$.
..# (use $3$): The piece on square $2$ moves to square $3$.
... (use $4$): The piece on square $3$ is removed. At this point, all the pieces have been removed.
Sample 2
Input
5 ....#
Output
1
Use $1$ of the magic removes the piece on square $5$.
Sample 3
Input
8 #.##..##
Output
9
#.##..## (initial)
.##.#.#. (use $1$)
.#.#.#.# (use $2$)
..#.#.#. (use $3$)
...#.#.# (use $4$)
....#.#. (use $5$)
.....#.# (use $6$)
......#. (use $7$)
.......# (use $8$)
........ (use $9$)
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。