레이팅 미적용베시가 'C', 'O', 'W'만으로 이루어진 평소의 문자열 가지고 노는 데 싫증이 나자, 농부 존은 그녀에게 'M'과 'O'만으로 이루어진 \(Q\)개의 새 문자열을 주었다 (\(1 \leq Q \leq 100\)). 'M'과 'O'로 만들 수 있는 베시가 가장 좋아하는 단어는 당연히 "MOO"이므로, 그녀는 다음 연산들을 사용해 \(Q\)개의 문자열 각각을 "MOO"로 바꾸고 싶어 한다.
- 첫 번째 또는 마지막 문자를 반대 문자로 바꾼다 ('M'은 'O'가 되고 'O'는 'M'이 된다).
- 첫 번째 또는 마지막 문자를 삭제한다.
안타깝게도 베시는 게을러서 꼭 필요한 것보다 많은 연산을 수행하고 싶지 않다. 각 문자열에 대해 "MOO"를 만드는 데 필요한 최소 연산 횟수를 구하고, 불가능하면 \(-1\)을 출력하도록 도와주자.
Problem credits: Aryansh Shrivastava
채점 방식
- 입력 2-4: 모든 문자열의 길이는 최대 \(3\)이다.
- 입력 5-11: 추가 제약이 없다.
Problem credits: Aryansh Shrivastava
첫째 줄에 \(Q\)의 값이 주어진다.
다음 \(Q\)개의 줄에는 각각 'M' 또는 'O'로만 이루어진 문자열이 하나씩 주어진다. 각 문자열의 길이는 1 이상 100 이하이다.
각 입력 문자열에 대한 답을 한 줄에 하나씩 출력한다.
3
MOMMOM
MMO
MOO4
-1
0A sequence of \(4\) operations transforming the first string into "MOO" is as
follows:
Replace the last character with O (operation 1)
Delete the first character (operation 2)
Delete the first character (operation 2)
Delete the first character (operation 2)
The second string cannot be transformed into "MOO." The third string is already
"MOO," so no operations need to be performed.
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > January > Bronze