페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5882
서브태스크

준하의 보드게임 2초 1024MB

문제

준하는 보드게임을 구입했다.

준하가 구입한 보드게임은 N+2개의 칸이 가로 일렬로 늘어선 형태를 하고 있으며, 이 칸에는 왼쪽 가장자리에서 오른쪽 가장자리로 0에서 N + 1까지 번호가 매겨진다.

처음에, 0번 칸과 N + 1번 칸에는 'X'가, i (1≤i≤N)번 칸에는 S_i가 적혀있다. (S_i는 문자 '.' 또는 '#'이다)

준하는 이 보드게임 판과 하나의 조각으로 놀고 있다. 처음에 조각은 A (1 ≤ A ≤ N)번째 칸에 오른쪽을 향한 상태로 놓여 있다. 준하는 1 초가 지날 때마다 조각을 조각이 현재 향하고 있는 방향으로 1 칸 이동시킨다.

이 보드게임에는 다음과 같은 규칙이 설정되어 있습니다.

  1. X가 쓰여진 칸에 조각이 도착하면 조각의 방향은 반전된다.

  2. .가 쓰여진 칸에 조각이 도착하면 아무 일도 일어나지 않는다.

  3. #이 쓰여진 칸에 조각이 도착하면 조각의 방향은 반전된다. 이 때 이 칸에 쓰여진 문자를 .로 변경한다. 따라서 이 칸에 조각이 다시 온다고 해도 방향은 반전되지 않는다.

조각의 반전이나 문자 변경에 걸리는 시간은 무시할 수 있다.

말이 초기 상태가 주어졌을 때, #가 쓰여진 칸이 모두 없어지기까지 걸리는 시간을 출력하는 프로그램을 작성하라.


입력

입력은 다음 형식으로 표준 입력에서 제공됩니다.

N A

S

[제한]

2 ≤ N ≤ 200\,000.

1 ≤ A ≤ N.

S는 길이 N의 문자열이고 i 번째 문자 (1≤i≤N)는 S_i다.

S_i는 문자 . 또는 #이다 (1 ≤ i ≤ N).

S_A는 문자 .이다.

S_i가 문자 #과 같은 i (1≤i≤N)가 최소 하나 존재한다.


출력

#가 쓰여진 칸이 모두 없어지기까지 걸리는 시간을 한 줄로 출력한다.


부분문제

번호 점수 조건
#140점

N \le 3\,000

#260점

추가 제한 없음


예제1

입력
73
.#.#..#
출력
8

시간이 지남에 따라 보드 판의 상태는 다음과 같이 바뀐다.

다만, 우측 방향의 조각이 놓인 칸을 >, 좌측 방향의 조각이 놓인 칸을 <로 나타낸다.

  1. X.#>#..#X

  2. X.#.<..#X

  3. X.#<...#X

  4. X.>....#X

  5. X..>...#X

  6. X...>..#X

  7. X....>.#X

  8. X.....>#X

  9. X......<X

따라서 8초 안에 #이 모두 없어지므로 8을 출력한다.


예제2

입력
41
.#.#
출력
7

시간이 지남에 따라 보드 판의 상태는 다음과 같이 바뀐다.

다만, 우측 방향의 조각이 놓인 칸을 >, 좌측 방향의 조각이 놓인 칸을 <로 나타낸다.

  1. X>#.#X

  2. X.<.#X

  3. X<..#X

  4. >...#X

  5. X>..#X

  6. X.>.#X

  7. X..>#X

  8. X...<X

따라서 7초 안에 #이 모두 없어지므로 7을 출력한다.


예제3

입력
66
#####.
출력
35

출처

JOI 2021 예선2

역링크