FEB

베시와 엘시는 마침내 농부 존을 몰아낼 음모를 꾸미고 있다! 그들은 \(N\) (\(1\le N\le 2\cdot 10^5\))개의 문자 메시지를 주고받으며 계획을 세운다. 그들의 대화는 길이 \(N\)의 문자열 \(S\)로 나타낼 수 있으며, \(S_i\)는 \(B\) 또는 \(E\)로, 각각 \(i\)번째 메시지를 베시 또는 엘시가 보냈음을 의미한다.

그러나 농부 존이 계획을 듣고 그들의 대화를 가로채려 한다. 따라서 \(S\)의 일부 문자는 \(F\)이며, 이는 농부 존이 메시지를 알아볼 수 없게 만들어 발신자를 알 수 없음을 의미한다.

알아볼 수 없는 문자가 없는 대화의 흥분 정도는 소가 연속으로 두 번 보낸 횟수, 즉 \(S\)에서 부분 문자열 \(BB\) 또는 \(EE\)가 등장하는 횟수이다. 원래 메시지의 흥분 정도를 구하고 싶지만, 농부 존이 가린 메시지들이 실제로 베시의 것인지 엘시의 것인지 알 수 없다. 모든 가능성에 대해, \(S\)의 가능한 모든 흥분 정도를 출력하라.

출제자: William Yue, Claire Zhang

배점

• 입력 4-8: \(N\le 10\)
• 입력 9-20: 추가 제약 조건이 없다.

출제자: William Yue, Claire Zhang

첫째 줄에 정수 \(N\)이 주어진다.

다음 줄에 \(S\)가 주어진다.

먼저 가능한 서로 다른 흥분 정도의 개수 \(K\)를 출력한다. 다음 \(K\)개의 줄에 흥분 정도를 증가하는 순서로 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2022-2023 > US Open > Bronze