📑 Qualification Round 2021

Task 1. Reversort

📓 Variant 1. Python Only

T=int(input())
for t in range(T):
    COST=0
    I=int(input())
    N=input()
    N=[int(n) for n in N.split()]
    for i in range(I-1):
        j=i+N[i:].index(min(N[i:]))
        if i==j:
            COST+=1 
        else:
            L=[N[k] for k in range(i)]
            L+=[N[j-k] for k in range(j-i+1)]
            L+=[N[k] for k in range(j+1,I)]
            COST+=j-i+1
            N=L
    print('Case #{}: {}'.format(t+1,COST))

📓 Variant 2. Python Only

T=int(input())
for t in range(T):
    COST=0
    I=int(input())
    ARR=[int(n) for n in input().split()]
    for i in range(I-1):
        j=i+ARR[i:].index(min(ARR[i:]))
        if i==j:
            COST+=1 
        else:
            ARR=ARR[:i]+ARR[i:j+1][::-1]+ARR[j+1:]
            COST+=j-i+1
    print('Case #{}: {}'.format(t+1,COST))

📓 Variant 1. SageMath Interactive

Task 2. Moons and Umbrellas

📓 Variant 1. Python Only

# 5pts, 11pts, 1pts, ✓ ✓ RE 
def cost(X,Y,S):
    return X*S.count('CJ')+Y*S.count('JC')
def cut(S):
    while 'CC' in S:
        S=S.replace('CC','C')
    while 'JJ' in S:
        S=S.replace('JJ','J')
    return S
def recursive_cost(X,Y,S):
    if len(S) < 2:
        return 0
    else:
        if '?' not in S[:2]:
            return cost(X,Y,S[:2])+recursive_cost(X,Y,S[1:])
        else:
            if (S[0]=='?'):
                return min(recursive_cost(X,Y,'C'+S[1:]),
                           recursive_cost(X,Y,'J'+S[1:]))
            else:
                return min(recursive_cost(X,Y,S[0]+'C'+S[2:]),
                           recursive_cost(X,Y,S[0]+'J'+S[2:]))
T=int(input())
for t in range(T):
    XYS=input().split()
    X,Y,S=int(XYS[0]),int(XYS[1]),XYS[2]
    S=cut(S)
    if (X < 0 or Y < 0):
        COST=recursive_cost(X,Y,S)
    else:
        COST=cost(X,Y,S.replace('?',''))
    print('Case #{}: {}'.format(t+1,COST))

📓 Variant 1. SageMath Interactive

📓 Variant 2. Python Only

def update_state(s,s0,state):
    curr_state={}
    for s1,s2,xy in [('C','J',Y),('J','C',X)]:
        if s==s2:
            curr_state[s1]=10**12
        elif s0==s1:
            curr_state[s1]=state[s1]
        elif s0==s2:
            curr_state[s1]=state[s2]+xy
        elif s0=='?':
            curr_state[s1]=min(state[s1],state[s2]+xy)
 #   print(curr_state)
    return s,curr_state
def cost(X,Y,S):
    return X*S.count('CJ')+Y*S.count('JC')
def cut(X,Y,S):
    while 'CC' in S:
        S=S.replace('CC','C')
    while 'JJ' in S:
        S=S.replace('JJ','J')
    if (X>=0 and Y>=0):
        S=S.replace('?','')
    return S
for T in range(int(input())):
    X,Y,S=input().split()
    X,Y=int(X),int(Y)
    S=cut(X,Y,S)
    if (X < 0 or Y < 0):
        s0,state=S[0],{'C':0,'J':0}
        for s in S[1:]:
            s0,state=update_state(s,s0,state)
        COST=min(state.values())
    else:
        COST=cost(X,Y,S)
    print('Case #%d: %s' %(T+1,COST))

📓 Variant 2. SageMath Interactive

Task 3. Reversort Engineering

📓 Variant 1. Python Only

def gen_permutate(n,c):
    if n==2:
        if c==1:
            return [1,2]
        else:
            return [2,1]
    else:
        base=gen_permutate(n-1,c-1)
        base=[1]+[base[i]+1 for i in range(n-1)]
        if c-1<=(n-1)*n//2-1:
            return base
        else:
            x=c-(n-1)*n//2+1
            return base[:x][::-1]+base[x:]
def gen_answer(n,cost):
    if cost < n-1 or cost > n*(n+1)//2-1:
        return 'IMPOSSIBLE'
    elif cost==n-1:
        arr=list(range(1,n+1))
        return str(arr)[1:-1].replace(',','')
    else:
        arr=gen_permutate(n,cost)
        return str(arr)[1:-1].replace(',','')
T=int(input())
for t in range(T):
    N,COST=map(int,input().split())
    ANS=gen_answer(N,COST)
    print('Case #{}: {}'.format(t+1,ANS))

📓 Variant 1. SageMath Interactive

Task 4. Median Sort

📓 Variant 1. Python Only

def median_sort(N):
    arr=[1,2]
    for i in range(3,N+1):
        l,r=0,len(arr)-1
        while r>l:
            m1,m2=l+(r-l)//3,r-(r-l)//3
            print(arr[m1],arr[m2],i,flush=True)
            a=int(input())
            if a==arr[m1]: 
                r=m1-1
                if l==r: r+=1
            elif a==arr[m2]: 
                l=m2+1
                if l==r: l-=1
            else:
                l,r=m1+1,m2-1
                if l==r: l-=1                
        arr.insert(l,i)
    print(' '.join(map(str,arr)),flush=True)
    answer=input()
    if answer!='1':  
        exit()
T,N,Q=map(int,input().split())
for t in range(T):
    median_sort(N)

📓 Variant 1. SageMath Interactive

Task 5. Cheating Detection

📓 Variant 1. Python Only

📓 Variant 1. SageMath Interactive