#PU1277. USACO 2023 January Contest, Bronze — Problem 3. Moo Operations

    ID: 1499 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 普及 上传者: 标签>USACO赛事:jan23来源:usaco.orgscoring:equal_test_cases贪心字符串

USACO 2023 January Contest, Bronze — Problem 3. Moo Operations

USACO 2023 January Contest, Bronze — Problem 3. Moo Operations

题目描述

Because Bessie is bored of playing with her usual text string where the only characters are 'C,' 'O,' and 'W,' Farmer John gave her QQ new strings (1≤Q≤1001 \leq Q \leq 100), where the only characters are 'M' and 'O.' Bessie's favorite word out of the characters 'M' and 'O' is obviously "MOO," so she wants to turn each of the QQ strings into "MOO" using the following operations: Replace either the first or last character with its opposite (so that 'M' becomes 'O' and 'O' becomes 'M'). Delete either the first or last character. Unfortunately, Bessie is lazy and does not want to perform more operations than absolutely necessary. For each string, please help her determine the minimum number of operations necessary to form "MOO" or output −1-1 if this is impossible.

输入格式

The first line of input contains the value of QQ. The next QQ lines of input each consist of a string, each of its characters either 'M' or 'O'. Each string has at least 1 and at most 100 characters.

输出格式

(见题面原文)

数据范围

Inputs 2-4: Every string has length at most 33. Inputs 5-11: No additional constraints. Problem credits: Aryansh Shrivastava

样例

样例 1

3
MOMMOM
MMO
MOO
4
-1
0
A 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.