USACO Jan 2023 B3 Moo Operations

USACO January 2023 Bronze Problem 3: Moo Operations¶

In [ ]:

# input from stdin
Q =  int(input())

_MEMO_=dict()
def recur(w,stepcount):

    # check if you have seen this input previously
    if w in _MEMO_:
        return _MEMO_[w]
    
    # Base Cases
    if len(w)<3:
        _MEMO_[w]=-1
        return(-1)
    elif len(w)==3:
        if w=="MOO":
            result = stepcount+0
        elif w[1]=="M":
            result = -1
        elif w=="OOO" or w=="MOM":
            result = stepcount+1
        elif w=="OOM":
            result = stepcount+2
        _MEMO_[w]=result
        return result  
            
    if len(w)>3:
        # PREPROCESSING STEP
        # consider delete first char only if second 2 last char is O
        if w[-2:-1]=='O':
            d1=recur(w[1:],stepcount)
        else:
            d1=-1
        # delete last char
        d2=recur(w[:-1],stepcount)

        if (d1>-1 and d2>-1):
            temp=min(d1,d2)
            result=temp+stepcount+1
        elif (d1==-1 and d2==-1):
            result=-1
        else:
            temp=max(d1,d2)
            result = temp+stepcount+1
        _MEMO_[w]=result
        return result 
    return(-1)

for x in range(Q):
    work = input()
    val = recur(work,0)
    # output to stdout
    print(val)