USACO 2023 January Contest Bronze Division - Moo Operations

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can brute force all possibilities to place the MOO, by fixing the middle character.

Then we find the best answer based on whether we have remaining characters from the MOO string next to our character.

Source codes

The source codes in C++ and Python can be seen below.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    while(n--)
    {
        string s;
        cin >> s;

        int ans = (1<<30);
        for(int i = 1; i + 1 < s.size(); i++)
        {
            if(s[i] == 'O')
            {
                int cost = s.size() - 3 + (s[i-1] == 'O') + (s[i+1] == 'M');
                ans = min(ans, cost);
            }
        }
        cout << (ans == (1<<30) ? -1 : ans) << '\n';
    }
    return 0;
}

t = int(input())
for _ in range(t):
    s = input().strip()
    ans = 1 << 30
    for i in range(1, len(s) - 1):
        if s[i] == 'O':
            cost = len(s) - 3 + (1 if s[i - 1] == 'O' else 0) + (1 if s[i + 1] == 'M' else 0)
            ans = min(ans, cost)
    print(-1 if ans == (1 << 30) else ans)