Участник:Ujify/thetwotowers

Материал из DISCOPAL
Перейти к: навигация, поиск

task: https://www.codechef.com/viewsolution/46705640

def lis1(L):
    n = len(L)
    lises = [1]*n
    for i in range(n):
        for j in range(i):
            if L[i]>L[j]and(lises[j]+1)>lises[i]:
                lises[i]=lises[j]+1
    return max(lises)
def smallest_index_greater(lisends,num,e):
    l = len(lisends)
    begin = 0
    end = e-1
    while end-begin>1:
        mid = (begin+end)//2
        if lisends[mid]>num:
            end = mid
        else:
            begin = mid
    return end
def lis(L):
    n = len(L)
    lisends = [0]*n
    lisends[0] = L[0]
    length = 1
    for i in L:
        if i<lisends[0]:
            lisends[0]=i
        elif i>lisends[length-1]:
            lisends[length]=i
            length += 1
        else:
 
            ind = smallest_index_greater(lisends,i,length)
            lisends[ind]=i
    return length
 
 
def lcs(X , Y):
    m = len(X)
    n = len(Y)
    L = [[None]*(n+1) for i in xrange(m+1)]
    for i in range(m+1):
        for j in range(n+1):
            if i == 0 or j == 0 :
                L[i][j] = 0
            elif X[i-1] == Y[j-1]:
                L[i][j] = L[i-1][j-1]+1
            else:
                L[i][j] = max(L[i-1][j] , L[i][j-1])
    return L[m][n]
n = int(raw_input())
inp = raw_input().split()
arr = [int(i) for i in inp]
l= len(arr)
inv = arr[::-1]
n1 = lis(arr)
n2=lis(inv)
if n1>n2:
    print 'Ajeyaa'
    print l-n1
elif n1==n2:
    print 'Both'
    print l-n1
else:
    print 'Sriram'
    print l-n2
    print