회의실 표시판의 분할 기록

문제

회의실 앞의 전자 표시판은 하루의 운영 시간을 길이가 같은 N개의 시간 칸으로 나누어 보여 준다. 각 시간 칸에는 예약이 없다는 뜻의 0 또는 예약이 있다는 뜻의 1이 기록되어 있다. 표시판 제어기는 이 기록을 보관할 때 정해진 분할 절차를 사용한다. N은 2의 거듭제곱이므로, 길이가 2 이상인 모든 처리 구간을 길이가 같은 두 구간으로 나눌 수 있다. 처음에는 N개의 시간 칸 전체를 하나의 처리 구간으로 잡는다. 처리 구간 안의 값이 모두 같으면 그 구간에 대한 보관 카드 한 장을 만들고 처리를 끝낸다. 카드에는 구간의 상태와 시작 위치, 길이를 적는다. 구간 안에 0과 1이 모두 있다면 그 구간 자체의 카드는 만들지 않는다. 대신 구간을 앞쪽 절반과 뒤쪽 절반으로 나누고, 각 절반에 똑같은 절차를 적용한다. 시간 칸 하나로 이루어진 구간은 언제나 값이 모두 같은 구간이다. 서로 이웃한 두 구간의 상태가 같더라도 이미 만들어진 카드를 나중에 합치는 작업은 하지 않는다. 어떤 구간을 나눌지는 오직 그 구간 안에 두 상태가 모두 있는지에 따라 결정된다. 또한 분할 위치를 임의로 옮기거나, 앞쪽과 뒤쪽의 길이를 다르게 정할 수 없다. 이 규칙에 따라 모든 시간 칸은 정확히 한 장의 최종 카드에 포함된다. 보관 공간을 계산하기 위해서는 카드 장수뿐 아니라 카드가 만들어진 깊이도 필요하다. 전체 구간의 깊이는 0이고, 구간을 한 번 나눌 때마다 자식 구간의 깊이는 부모보다 1 커진다. 카드 한 장이 차지하는 보관 단위는 그 카드의 깊이에 1을 더한 값이다. 최종적으로 만들어지는 0 카드의 장수, 1 카드의 장수, 모든 카드의 보관 단위 합을 구한다. 카드의 실제 시작 위치와 길이는 출력하지 않는다.

입력

첫째 줄에 정수 N이 주어진다. N = 2^p를 만족하는 정수 p가 존재하며 0 ≤ p ≤ 17이다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S의 각 문자는 0 또는 1이며, 왼쪽부터 시간 순서대로 표시판의 상태를 나타낸다.

출력

0 카드의 장수, 1 카드의 장수, 모든 카드의 보관 단위 합을 순서대로 공백으로 구분하여 한 줄에 출력한다. 특정 상태의 카드가 없으면 해당 장수는 0으로 출력한다.

8
00001101

2 2 13

1
1

0 1 1

4
0101

2 2 12

출처: Devin.KR 자체 제작