레이팅 미적용베시(Bessie)의 컴퓨터에는 M과 O, 단 두 글자만 있는 키보드가 달려 있다.
베시는 각 글자가 M 또는 O인 \(N\)개의 글자로 이루어진, 가장 좋아하는 음머 \(S\)를 입력하고 싶어 한다. 하지만 베시의 컴퓨터는 바이러스에 감염되었다. 베시가 O를 입력하려고 할 때마다, 그 O가 나타나기 전에 지금까지 입력된 모든 글자가 M은 O로, O는 M으로 뒤집힌다.
베시가 가장 좋아하는 음머를 입력하는 것이 가능한가?
추가로, 베시에게는 \(0\) 또는 \(1\)인 매개변수 \(k\)가 주어진다.
- \(k = 0\)이면, 베시는 가장 좋아하는 음머를 입력할 수 있는지만 판정하면 된다.
- \(k = 1\)이면, 베시는 가장 좋아하는 음머를 입력하기 위한 키 입력 순서의 예시도 제시해야 한다.
문제 제공: Nick Wu
배점
- 입력 3-4: \(k=0\).
- 입력 5-6: \(k=1, T \le 10^3, N \le 10\).
- 입력 7-9: \(k=1, T \le 10, N \le 1000\).
- 입력 10-16: \(k=1\).
문제 제공: Nick Wu
첫째 줄에 독립적인 테스트 케이스의 수 \(T\) (\(1\le T\le 10^4\))와 \(k\) (\(0 \le k \le 1\))가 주어진다.
각 테스트 케이스의 첫째 줄에 \(N\) (\(1 \le N \le 2 \cdot 10^5\))이 주어진다.
각 테스트 케이스의 둘째 줄에 \(S\)가 주어진다. \(S\)에는 \(\texttt{M}\)과 \(\texttt{O}\) 외의 문자가 나타나지 않음이 보장된다.
모든 테스트 케이스에 대한 \(N\)의 합은 \(4 \cdot 10^5\)을 넘지 않는다.
각 테스트 케이스에 대해, 다음 절차에 따라 한 줄 또는 두 줄을 출력한다.
베시가 \(S\)를 입력하는 것이 불가능하면, 한 줄에 \(\texttt{NO}\)를 출력한다.
그렇지 않으면, 첫째 줄에 \(\texttt{YES}\)를 출력한다. 나아가 \(k=1\)이면, 둘째 줄에 베시가 가장 좋아하는 음머를 입력하기 위해 순서대로 눌러야 하는 글자들로 이루어진 길이 \(N\)의 문자열을 출력한다. 그러한 문자열이 여러 개라면 아무것이나 출력해도 정답으로 인정된다.
2 0
3
MOO
5
OOMOOYES
YES2 1
3
MOO
5
OOMOOYES
OMO
YES
MOOMOAs Bessie types out \(\texttt{MOOMO}\), this is how the letters change:
- Before typing the first \(\texttt{M}\), Bessie has an empty string. Afterwards, she has the string \(\texttt{M}\).
- After typing the first \(\texttt{O}\), the \(\texttt{M}\) flips to \(\texttt{O}\), and then the \(\texttt{O}\) is appended to form \(\texttt{OO}\).
- After typing the second \(\texttt{O}\), the \(\texttt{OO}\) flips to \(\texttt{MM}\), and then the \(\texttt{O}\) is appended to form \(\texttt{MMO}\).
- After typing the second \(\texttt{M}\), Bessie has the string \(\texttt{MMOM}\).
- After typing the last \(\texttt{O}\), the string \(\texttt{MMOM}\) flips to \(\texttt{OOMO}\), and then the \(\texttt{O}\) is appended to form \(\texttt{OOMOO}\), as desired.
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Second Contest > Bronze