iktk   2년 전

Blitz는 나무늘보들에게 울타리를 칠하라고 명령하려고 합니다.

울타리는 일렬로 서 있는 $n$개의 보드로 구성되어 있습니다. 처음에 모든 보드는 페인트가 칠해지지 않은 상태입니다.

나무늘보들이 울타리를 칠하는 알고리즘은 다음과 같습니다.

나무늘보들은 처음에 $n$개의 보드 중 하나 앞에 서서 작업을 시작하며, 처음에 서 있는 보드를 칠합니다. Blitz가 명령을 한 번 내리면, 모든 나무늘보들은 한 칸씩 오른쪽으로 이동합니다. 이동한 후에 나무늘보의 앞에 있는 보드가 아직 칠해지지 않았다면 즉시 칠합니다.

만약 보드가 칠해져 있다면 나무늘보는 아무 것도 하지 않습니다.

Blitz는 0번 이상의 명령을 내리며, 나무늘보가 $n$번째 보드보다 오른쪽에 가게 해서는 안 됩니다.

Blitz가 칠하고 싶은 무늬가 정해져 있지만, 나무늘보가 몇 마리나 있는지를 몰라서 나무늘보가 $1$마리인 경우부터 $n$마리인 경우까지 모든 경우의 수에 대해 작업 소요 시간을 계산하려고 합니다.

입력

첫 번째 줄에는 울타리를 구성하는 보드의 수를 나타내는 양의 정수 $n$ ($1 \le n \le 10^6$)이 주어집니다.

다음 줄에는 `#` 또는 `.`으로 구성된 길이 $n$의 문자열이 주어집니다. 이 문자열은 Blitz가 원하는 울타리의 최종 형태입니다. `#`은 칠해진 보드, `.`은 칠해지지 않은 보드를 의미합니다.

출력

한 줄에 $n$개의 정수를 공백으로 구분하여 출력합니다.

$i$번째 숫자는 나무늘보 $i$마리를 적절하게 배치했을 때 Blitz가 내려야 하는 명령 수의 최솟값입니다. 만약 불가능한 경우에는 그 대신 $-1$을 출력합니다.

wizardrabbit   2년 전

입력 범위 $n$ ($1 \le n \le 10^6$) 뒤에 j를 흘리신 것 같아요

iktk   2년 전

@wizardrabbit

j를 주웠습니다. 감사합니다.

댓글을 작성하려면 로그인해야 합니다.