시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 79 33 32 64.000%

문제

제이크는 레이니콘으로부터 긴 모양의 케이크를 선물 받았습니다. 

케이크 위에는 N개의 과일 조각이 올려져 있는데 케이크 위에는 딸기 N/2개와 키위 N/2개가 일정한 간격을 두고 일렬로 올려져 있습니다. 여기서 N은 4의 배수입니다.

제이크는 케이크를 핀과 올려진 과일의 종류를 포함하여 케이크를 정확히 절반씩 먹기 위해 받은 케이크를 잘라서 나누어 가지려고 합니다. 이때 제이크가 받은 딸기가 N/4개여야 하며 키위도 N/4개 있어야 합니다. 핀도 제이크와 같은 개수의 딸기와 키위를 받아야 합니다.

제이크와 핀은 케이크를 자르기 귀찮으므로 그 횟수를 최소화하고자 합니다. 핀과 제이크가 똑같이 나누어 먹기 위해 케이크를 잘라야 하는 최소 횟수와 방법을 알려주세요.

입력

첫 번째 줄에는 케이크 위에 있는 과일의 개수 N (4 ≤ N ≤ 200,000) 이 주어집니다.

두 번째 줄에는 케이크의 정보가 담긴 길이가 N인 문자열이 주어집니다. i번째 문자가 's'이면 i번째 칸에는 딸기가 'k'이면 키위가 올려져 있음을 의미합니다.

출력

첫 번째 줄에 최소 횟수 k (1 ≤ k- 1) 를 출력합니다.

두 번째 줄에는 k개의 정수 c1, c2, ..., ck (1 ≤ c1 < c2 < ... < ck  ≤ - 1) 를 출력합니다. 여기서 cic번째 과일이 있는 곳과 c+1번째 과일이 있는 곳 사이를 자른다는 의미입니다.

자르는 방법이 여러 개인 경우 그 중 하나만 출력합니다.

예제 입력 1

4
skks

예제 출력 1

1
2

예제 입력 2

8
sskskksk

예제 출력 2

2
1 5

c1 = 1번째 과일과 2번째 과일 사이를 자르고 c= 5번째 과일과 6번째 과일 사이를 잘라서 총 k = 2 번의 칼질로 케이크를 공평하게 나눌 수 있습니다.

출처

University > 경북대학교 > 2018 Goricon 🐶번

  • 문제를 만든 사람: exqt