Problem:
 Score : 100 points    Problem Statement You are given strings s and t .
Find one longest string that is a subsequence of both s and t .      Notes A subsequence of a string x is the string obtained by removing zero or more characters from x and concatenating the remaining characters without changing the order.      Constraints  s and t are strings consisting of lowercase English letters.  1 \leq |s|, |t| \leq 3000         Input Input is given from Standard Input in the following format:  s  t       Output Print one longest string that is a subsequence of both s and t .
If there are multiple such strings, any of them will be accepted.        Sample Input 1 axyb
abyxb      Sample Output 1 axb  The answer is axb or ayb ; either will be accepted.       Sample Input 2 aa
xayaz      Sample Output 2 aa       Sample Input 3 a
z      Sample Output 3   The answer is (an empty string).       Sample Input 4 abracadabra
avadakedavra      Sample Output 4 aaadara

Solution (Python):
S = input()
T = input()

ls = len(S)
lt = len(T)

DP = [[0] * (ls+1) for _ in range(lt+1)]

for i in range(lt):
    for j in range(ls):
        if T[i] == S[j]:
            DP[i+1][j+1] = DP[i][j] + 1
        else:
            DP[i+1][j+1] = max(DP[i+1][j], DP[i][j+1])

ans = ''
while ls * lt > 0:
    if DP[lt][ls] == DP[lt-1][ls]:
        lt -= 1
    elif DP[lt][ls] == DP[lt][ls-1]:
        ls -= 1
    elif DP[lt][ls] == DP[lt-1][ls-1] + 1:
        lt -= 1
        ls -= 1
        ans += S[ls]
print(ans[::-1])

Solution (Python):
s1 = list(input())
s2 = list(input())

dp = [[0] * (len(s2) + 1) for i in range(len(s1) + 1)]

s1.insert(0, ' ')
s2.insert(0, ' ')


max_len = 0
for i in range(1, len(s1)):
    for j in range(1, len(s2)):
        if s1[i] == s2[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        max_len = max(max_len, dp[i][j])


ans = []
i = len(s1)-1
j = len(s2)-1
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        ans.insert(0, s1[i])
        i -= 1
        j -= 1
print(''.join(ans))

Solution (Python):
s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
for i in range(slen):
  for j in range(tlen):
    if s[i] == t[j]:
      dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
result = ''
i = slen
j = tlen
while i > 0 and j > 0:
  if dp[i - 1][j] == dp[i][j]:
    i -= 1
  elif dp[i][j - 1] == dp[i][j]:
    j -= 1
  else:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)

Solution (Python):

def main():
    S, T = tuple(input().rstrip() for _ in range(2))
    n, m = len(S), len(T)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if S[i - 1] == T[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
    ans = []
    while n > 0 and m > 0:
        if dp[n][m] == dp[n - 1][m]:
            n -= 1
        elif dp[n][m] == dp[n][m - 1]:
            m -= 1
        else:
            n -= 1
            m -= 1
            ans += [S[n]]
    print(*ans[::-1], sep="")


if __name__ == "__main__":
    main()

Solution (Python):
def solve():
    s, t = read()
    result = think(s, t)
    write(result)


def read():
    return read_line(), read_line()


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(s, t):
    
    local_s = ' ' + s  
    local_t = ' ' + t
    dp = [[0 for x in range(len(local_s))] for y in range(len(local_t))]

    for y, ct in enumerate(local_t):
        for x, cs in enumerate(local_s):
            if x == 0 or y == 0:
                dp[y][x] = 0
            else:
                if local_s[x] == local_t[y]:
                    dp[y][x] = dp[y - 1][x - 1] + 1
                else:
                    dp[y][x] = max(dp[y - 1][x], dp[y][x - 1], dp[y - 1][x - 1])

    
    x = len(dp[0]) - 1
    y = len(dp) - 1
    buf = ''

    while x > 0 and y > 0:
        if local_s[x] == local_t[y]:
            buf += local_s[x]
            x -= 1
            y -= 1
        else:
            if dp[y][x] == dp[y - 1][x]:
                y -= 1
            else:
                x -= 1

    buf = list(buf)
    buf.reverse()
    return ''.join(buf)


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
input=sys.stdin.readline
s=' '+input().rstrip()
t=' '+input().rstrip()
m=len(s)-1
n=len(t)-1
dp=[[0]*(n+1) for i in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        if s[i]==t[j]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
ans=''
while m>0 and n>0:
    if dp[m][n]==dp[m][n-1]:
        n-=1
    elif dp[m][n]==dp[m-1][n]:
        m-=1
    elif dp[m][n]==dp[m-1][n-1]+1:
        ans=s[m]+ans
        m-=1
        n-=1
print(ans)

Solution (Python):
s = input()
t = input()


dp = [[0] * (len(t)+1) for i in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
        else:
            dp[i+1][j+1] = max(dp[i+1][j+1], max(dp[i][j+1], dp[i+1][j]))




i = len(s)
j = len(t)


ans = ""
while (i > 0) and (j > 0):
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans += s[i-1]
        i -= 1
        j -= 1

print(ans[::-1])

Solution (Python):
import sys
input=sys.stdin.readline

S = input().rstrip()
T = input().rstrip()
DP = [[0]*(len(T)+1) for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            DP[i+1][j+1] = DP[i][j]+1
        else:
            DP[i+1][j+1] = max(DP[i+1][j],DP[i][j+1])

m,n = len(S),len(T)
ans = ''
while m>0 and n>0:
    if DP[m][n] == DP[m][n-1]:
        n-=1
    elif DP[m][n] == DP[m-1][n]:
        m -= 1
    else:
        m,n = m-1,n-1
        ans = T[n]+ans
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
s=' '+input().rstrip()
t=' '+input().rstrip()
m=len(s)-1
n=len(t)-1
dp=[[0]*(n+1) for i in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        if s[i]==t[j]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
ans=''
while m>0 and n>0:
    if dp[m][n]==dp[m][n-1]:
        n-=1
    elif dp[m][n]==dp[m-1][n]:
        m-=1
    elif dp[m][n]==dp[m-1][n-1]+1:
        ans=s[m]+ans
        m-=1
        n-=1
print(ans)

Solution (Python):
s = " " + input()
t = " " + input()

dp = [[0 for _ in range(len(t))] for _ in range(len(s))]

for i in range(1, len(s)):
    for j in range(1, len(t)):
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + (1 if s[i] == t[j] else 0))

i = len(s) - 1
j = len(t) - 1
c = 0
ans = []
ansl = dp[-1][-1]
while (c < ansl):
    if s[i] == t[j]:
        ans.append(s[i])
        i -= 1
        j -= 1
        c += 1
    else:
        if dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
ans.reverse()
print("".join(ans))

Solution (Python):
s = str(input())
t = str(input())
s_length = len(s) 
t_length = len(t)

if s_length < t_length:
    s, t = t, s
    s_length, t_length = t_length, s_length

dp = [[0 for j in range(s_length + 1)] for i in range(t_length + 1)]

for i in range(0, t_length):
    for j in range(0, s_length):
        if s[j] == t[i]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

lcs = ""
i = t_length
j = s_length

while (i > 0 and j > 0):
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        lcs += s[j-1]
        i -= 1
        j -= 1

print(lcs[::-1])

Solution (Python):
import math
import sys

S = sys.stdin.readline()[:-1]
T = sys.stdin.readline()[:-1]
sl = len(S)
tl = len(T)
dp = [[0 for _ in range(tl + 1)] for _ in range(sl + 1)]


ans = ""
for s_ind in range(sl):
    for t_ind in range(tl ):
        if S[s_ind]  == T[t_ind]:
            dp[s_ind + 1][t_ind + 1] = dp[s_ind ][t_ind ] + 1   

        dp[s_ind + 1][t_ind + 1]  = max(dp[s_ind + 1][t_ind + 1],dp[s_ind + 1][t_ind  ],dp[s_ind][t_ind+ 1])

i = sl
j = tl
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j- 1]:
        j -=1
    elif dp[i][j] == dp[i - 1][j]:
        i -=1
    else:
        ans = S[i -1 ] + ans
        i -=1
        j -=1


print(ans)

Solution (Python):
s,t=input(),input()
ls,lt=len(s),len(t)
dp=[[0]*(lt+1) for _ in range(ls+1)]
for i in range(1,ls+1):
  for j in range(1,lt+1):
    if s[i-1]==t[j-1]:dp[i][j]=dp[i-1][j-1]+1
    else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])
l=dp[-1][-1]
i,j,a=ls,lt,""
while l!=0:
  if dp[i][j]==dp[i][j-1]:j-=1
  elif dp[i][j]==dp[i-1][j]:i-=1
  else:a=s[i-1]+a;i-=1;j-=1;l-=1
print(a)

Solution (Python):
s=input()
t=input()
n=len(s)
m=len(t)
s1=''
dp=[[0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(n+1):
  for j in range(m+1):
    if i==0 or j==0:
      continue
    if s[i-1]==t[j-1]:
    
      dp[i][j]=1+dp[i-1][j-1]
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])
l=dp[n][m]
i=n
j=m
while(i>=0 and j>=0):
    if s[i-1]==t[j-1]:
      s1+=s[i-1]
      i-=1
      j-=1
    elif dp[i][j-1]>dp[i-1][j]:
      j-=1
    else:
      i-=1
s2=''
for u in range(dp[n][m]-1,-1,-1):
  s2+=s1[u]
print(s2)

Solution (Python):
if __name__ == '__main__':
    s = input()
    t = input()

    dp = [[0 for _ in range(len(s) + 1)] for _ in range(len(t) + 1)]

    for i in range(len(t)):
        for j in range(len(s)):
            if t[i] == s[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

    r = []

    li, lj = len(t), len(s)

    while li != 0 and lj != 0:
        if t[li - 1] == s[lj - 1]:
            r.append(t[li - 1])
            li -= 1
            lj -= 1
        elif dp[li][lj - 1] > dp[li - 1][lj]:
            lj -= 1
        else:
            li -= 1

    print("".join(r[::-1]))

Solution (Python):
s = input()
t = input()

dp = [[0 for i in range(len(t) + 1)] for j in range(len(s) + 1)]

for i in range(1, len(s) + 1):
    for j in range(1, len(t) + 1):
        if s[i - 1] == t[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

ans = ''

ls = len(s)
lt = len(t)

while ls != 0 and lt != 0:
    if s[ls - 1] == t[lt - 1]:
        ans += s[ls - 1]
        ls -= 1
        lt -= 1
    
    elif dp[ls][lt - 1] > dp[ls - 1][lt]:
        lt -= 1
    
    else:
        ls -= 1

print(ans[::-1])

Solution (Python):
S = input()
T = input()

dp = [[0] * (len(T)+1) for _ in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

res = ""
i = len(S)
j = len(T)

while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        res = S[i-1] + res
        i -= 1
        j -= 1

print(res)

Solution (Python):
def lcs(s,t):
    n=len(s)
    m=len(t)
    dp=[[0 for i in range(n+1)]for j in range(m+1)]
    st=""
    for i in range(m+1):
        for j in range(n+1):
            if(i==0 or j==0):
                dp[i][j]=0
            elif(t[i-1]==s[j-1]):
                dp[i][j]=max(1+dp[i-1][j-1],dp[i][j])
            elif(t[i-1]!=s[j-1]):
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    
    x=dp[m][n]
    lcs=[""]*(x+1)
    lcs[x]=""
    i=m
    j=n
    tmp=x
    while(i>0 and j>0):
        if(t[i-1]==s[j-1]):
            lcs[x-1]=t[i-1]
            i-=1
            j-=1
            x-=1
        elif(dp[i-1][j]>=dp[i][j-1]):
            i-=1
        else:
            j-=1
    
    for i in range(tmp+1):
        st=st+lcs[i]
    return st      


s=input()
t=input()
print(lcs(s,t))

Solution (Python):


def f():
    s = input()
    t = input()
    ls, lt = len(s), len(t)
    dp = [[0]*(ls+1) for _ in range(lt+1)]
    for i in range(lt):
        for j in range(ls):
            if t[i] == s[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
                
    ans = ""
    while lt > 0 and ls > 0:
        if dp[lt][ls] == dp[lt-1][ls]:
            lt -= 1
        elif dp[lt][ls] == dp[lt][ls-1]:
            ls -= 1
        elif dp[lt][ls] == dp[lt-1][ls-1] + 1:
            ans += t[lt-1]
            lt -= 1
            ls -= 1
    print(ans[::-1])
    
if __name__ == "__main__":
    f()

Solution (Python):
s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(n):
  for j in range(m):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j] + 1
    else:
      dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
i,j = n,m
ans = ""
while i and j:
  if dp[i][j] == dp[i-1][j]:
    i -= 1
  elif dp[i][j] == dp[i][j-1]:
    j -= 1
  else:
    i -= 1
    j -= 1
    ans += s[i]
print(ans[::-1])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007


def A():
    """
    N個の足場があります。足場には1,2,…,Nと番号が振られています。 
    各i (1≤i≤N) について、足場 i の高さは hi です。
    最初、足場 1 にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。
    足場 i にいるとき、足場 i+1 または i+2 へジャンプする。
    このとき、ジャンプ先の足場を j とすると、コスト |hi−hj| を支払う。
    カエルが足場 N に辿り着くまでに支払うコストの総和の最小値を求めてください。

    制約
        入力はすべて整数である。
    2≤N≤10**5
    1≤hi≤10**4
    """
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]))
    print(dp[n-1])
    return


def B():
    n, K = LI()
    h = LI()
    dp = [float("INF") for i in range(n + K + 1)]
    dp[0] = 0
    for i in range(n):
        for k in range(1, K + 1):
            if i + k >= n:
                break
            dp[i + k] = min(dp[i + k], dp[i] + abs(h[i] - h[i + k]))
    print(dp[n-1])
    return


def C():
    n = II()
    abc = LIR(n)
    dp = [0 for i in range(3 * n + 1)]
    dp[0] = abc[0][0]
    dp[1] = abc[0][1]
    dp[2] = abc[0][2]
    for i in range(1,n):
        dp[3 * i] = max(dp[3 * i], dp[3 * (i - 1) + 1] + abc[i][0], dp[3 * (i - 1) + 2] + abc[i][0])
        dp[3 * i + 1] = max(dp[3 * i + 1], dp[3 * (i - 1) + 2] + abc[i][1], dp[3 * (i - 1)] + abc[i][1])
        dp[3 * i + 2] = max(dp[3 * i + 2], dp[3 * (i - 1) + 1] + abc[i][2], dp[3 * (i - 1)] + abc[i][2])
    dp[3 * n] = max(dp)
    print(dp[3*n])

    return


def D():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**5
    1≤wi≤W
    1≤vi≤10**9"""
    n, w = LI()
    wv = LIR(n)
    dp = [[0 for k in range(w + 1)] for i in range(n + 2)]
    for i in range(1,n + 1):
        for j in range(w + 1):
            if j < wv[i-1][0]:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - wv[i - 1][0]] + wv[i - 1][1])
    print(dp[n+1][w])

    
    return


def E():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**9
    1≤wi≤W
    1≤vi≤10**3"""
    n, w = LI()
    wv = LIR(n)
    dp = [[float("INF") for i in range(10 ** 5 + 1)] for k in range(n + 1)]
    dp[0][0] = 0
    for i in range(n):
        for k in range(10 ** 5 + 1):
            if k < wv[i][1]:
                dp[i + 1][k] = dp[i][k]
            else:
                dp[i + 1][k] = min(dp[i][k], dp[i][k - wv[i][1]] + wv[i][0])
    ans = 0
    for i in range(10 ** 5 + 1):
        if dp[n][i] <= w:
            ans = i
    print(ans)

    return


def F():
    s = S()
    t = S()
    dp = [[0 for i in range(len(t)+1)] for k in range(len(s)+1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                if dp[i][j + 1] < dp[i + 1][j]:
                    dp[i + 1][j + 1] = dp[i + 1][j]
                else:
                    dp[i + 1][j + 1] = dp[i][j + 1]
    ss = len(s)
    tt = len(t)
    ans = ""
    si = ss
    ti = tt
    while si > 0 and ti > 0:
        if dp[si][ti] == dp[si - 1][ti]:
            si -= 1
        elif dp[si][ti] == dp[si][ti - 1]:
            ti -= 1
        else:
            si -= 1
            ti -= 1
            ans = s[si]+ans


    print(ans)
    return


def G():
    n, m = LI()
    xy = LIR_(m)
    edge = [[] for i in range(n)]
    for x,y in xy:
        edge[x].append(y)
    dp = [0 for i in range(n)]
    def ans(dp, i):
        
        if dp[i] != 0:
            return dp[i]
        else:
            if len(edge[i]) == 0:
                return 0
            ansb = 0
            for k in edge[i]:
                
                ansb = max(ansb, ans(dp, k) + 1)
                dp[i] = max(ansb, dp[i])
                
            return ansb
            
    for i in range(n):
        dp[i] = ans(dp, i)
    print(max(dp))
    return


def H():
    h, w = LI()
    a = SR(h)
    dp = [[0 for i in range(w)] for k in range(h)]
    for i in range(w):
        if a[0][i] == "
            break
        dp[0][i] = 1
    for i in range(h):
        if a[i][0] == "
            break
        dp[i][0] = 1
    for i in range(1,w):
        for k in range(1, h):
            
            if a[k - 1][i] == ".":
                if a[k][i - 1] == ".":
                    dp[k][i] = dp[k - 1][i] + dp[k][i - 1] % mod
                else:
                    dp[k][i] = dp[k - 1][i]
            else:
                if a[k][i - 1] == ".":
                    dp[k][i] = dp[k][i - 1]
    print(dp[h-1][w-1] % mod)

    return


def I():
    n = II()
    p = LF()
    dp = [[0 for k in range(n+1)] for i in range(n+1)]
    dp[1][1] = p[0]
    dp[1][0] = 1-p[0]
    for i in range(2,n+1):
        for k in range(i + 1):
            if k == 0:
                
                dp[i][k] = dp[i-1][k] * (1 - p[i-1])
            else:
                dp[i][k] = dp[i - 1][k - 1] * p[i - 1] + dp[i - 1][k] * (1 - p[i - 1])
    
    print(sum(dp[n][n//2+1:]))
    return 

def J():
    n = II()
    a = LI()



def K():
    n, k = LI()
    an = LI()
    dp = [0 for i in range(k + 1)]
    dp[0] = 0
    ans = ["First","Second"]
    for i in range(k + 1):
        if i in an:
            dp[i] = 0
        else:
            for num, a in enumerate(an):
                if a < i:
                    if dp[i - a] == 1:
                        dp[i] = 0
                        break
            else:
                dp[i] = 1
        

    print(ans[dp[k]])


def L():
    N, K = LI()
    an = LI()
    dp = [[1 for k in range(K + 2)] for n in range(N)]
    an.sort()
    for a in range(K + 2):
        if a == 0:
            continue
        elif a <= an[0]:
            dp[0][a] = (dp[0][a - 1] + 1) % mod
    for n in range(1,N):
        for k in range(1,K + 2):
            if k - an[n] <= 0:
                dp[n][k] = (dp[n - 1][k] + dp[n][k - 1]) % mod
            else:
                dp[n][k] =  dp[n][k-1] + (dp[n - 1][k] - dp[n - 1][k - an[n]]) % mod
    print(dp)


















if __name__ == '__main__':
    F()

Solution (Python):

import sys
def S(): return list(sys.stdin.readline())[:-1]
def f():
    s = S()
    t = S()
    ls = len(s)
    lt = len(t)
    dp = [[0]*(ls+1) for _ in range(lt+1)]
    for i in range(lt):
        for j in range(ls):
            if t[i] == s[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])

    ans = ""
    while lt > 0 and ls > 0:
        if dp[lt][ls] == dp[lt-1][ls]:
            lt -= 1
        elif dp[lt][ls] == dp[lt][ls-1]:
            ls -= 1
        elif dp[lt][ls] == dp[lt-1][ls-1] + 1:
            ans += t[lt-1]
            lt -= 1
            ls -= 1
    print(ans[::-1])

if __name__ == '__main__':
    f()

Solution (Python):

s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0 for _ in range(ls+1)] for _ in range(lt+1)]

for i in range(lt):
    for j in range(ls):
        if t[i] == s[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])

ans = ""
ti = lt
sj = ls
while ti > 0 and sj > 0:
    if dp[ti][sj] == dp[ti-1][sj]:
        ti -= 1
    elif dp[ti][sj] == dp[ti][sj-1]:
        sj -= 1
    elif dp[ti][sj] == dp[ti-1][sj-1] + 1:
        ans += t[ti-1]
        ti -= 1
        sj -= 1
print(ans[::-1])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
def factorial(n):
    if (n==0) or (n==1):
        return 1
    ret = 1
    for i in range(2, n+1):
        ret *= i
    return ret
def combination(n, k):
    return factorial(n)//factorial(k)//factorial(n-k)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

s = S()
t = S()


dp = [[0]*(len(t)+1) for i in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if (s[i] == t[j]):
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

i = len(s)
j = len(t)
res = ""
while (i>0  and j>0):
    if (dp[i][j] == dp[i-1][j]):
        i -= 1
    elif (dp[i][j] == dp[i][j-1]):
        j -= 1
    else:
        i -= 1
        j -= 1
        res = s[i] + res

print(res)

Solution (Python):
s=list(input())
t=list(input())

lens=len(s)
lent=len(t)

dp=[[0]*(lent+1) for _ in range(lens+1)]

for i in range(lens):
    for j in range(lent):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])

ans=''
i,j=lens,lent

while i>=0 and j>=0:
    if dp[i-1][j]==dp[i][j]:i-=1
    elif dp[i][j-1]==dp[i][j]:j-=1
    else:
        ans=s[i-1]+ans
        i,j=i-1,j-1
print(ans)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

s = input()
t = input()

Ls = len(s)+1
Lt = len(t)+1

dp = [[0]*Lt for _ in range(Ls)]

for i in range(1,Ls):
    for j in range(1,Lt):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])

i,j = Ls-1, Lt-1
ans = ''
while i >= 0 and j >= 0:
    if dp[i-1][j] == dp[i][j]:
        i -= 1
    elif dp[i][j-1] == dp[i][j]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i,j = i-1,j-1

print(ans)

Solution (Python):
a="0"+input()
b="1"+input()
dp=[[0]*len(b) for i in range(len(a))]
for i in range(len(a)):
    for j in range(len(b)):
        if a[i]==b[j]:
            if i>0 and j>0:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=1
        else:
            if i>0 and j>0:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
            elif i==0 and j>0:
                dp[i][j]=dp[i][j-1]
            elif i>0 and j==0:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=0

ans = []
x,y=len(a)-1,len(b)-1
lcs = dp[x][y]
while x > 0 or y > 0:
    if x-1 >= 0 and dp[x-1][y] == lcs:
        x -= 1
    elif y-1 >= 0 and dp[x][y-1] == lcs:
        y -= 1
    else:
        ans.append(a[x])
        y -= 1
        x -= 1
        
        lcs -= 1
print("".join(ans[::-1]))

Solution (Python):

"""
F - LCS
https://atcoder.jp/contests/dp/tasks/dp_f

"""
import sys


def solve(s, t):
    n, m = len(s), len(t)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n):
        for j in range(m):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
    ans = []
    y, x = n, m
    lcs = dp[y][x]
    while x > 0 or y > 0:
        if y-1 >= 0 and dp[y-1][x] == lcs:
            y -= 1
        elif x-1 >= 0 and dp[y][x-1] == lcs:
            x -= 1
        else:
            y -= 1
            x -= 1
            ans.append(s[y])
            lcs -= 1
    return ''.join(ans[::-1])


def main(args):
    s = input()
    t = input()
    ans = solve(s, t)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
s = input()
t = input()

lens = len(s)
lent = len(t)




















shift = [1 << x for x in range(3000 + 1)]

dp = [[0] * (lent + 1) for _ in range(lens + 1)]
for aindex in range(lens - 1, -1, -1):
    for bindex in range(lent - 1, -1, -1):
        if s[aindex] == t[bindex]:
            r = dp[aindex + 1][bindex + 1] + 1
        else:
            r = max(dp[aindex + 1][bindex], dp[aindex][bindex + 1])
        dp[aindex][bindex] = r

ans = ""
ls = len(s)
lt = len(t)
ls = 0
lt = 0
while ls < lens and lt < lent:
    if dp[ls][lt] == dp[ls + 1][lt]:
        ls += 1
    elif dp[ls][lt] == dp[ls][lt + 1]:
        lt += 1
    else:
        ans += t[lt]
        ls += 1
        lt += 1
print(ans)

Solution (Python):


import sys

class FLCS:
    def solve(self):
        s = input()
        t = input()
        n = len(s)
        m = len(t)
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        dp[0][0] = 0
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        ans = ""
        cur = max(dp[-1])
        cur_index = -float('inf')
        for i in range(n, 0, -1):
            if cur == 0:
                break
            if cur in dp[i] and (cur not in dp[i - 1] or dp[i - 1].index(cur) >= cur_index):
                index = dp[i].index(cur)
                ans += t[index - 1]
                cur -= 1
                cur_index = index

        print(ans[::-1])

solver = FLCS()
input = sys.stdin.readline

solver.solve()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

s = input()
t = input()

n = len(s)
m = len(t)

dp = [[0]*(m+1) for _ in range(n+1)]

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i][j] + 1, dp[i][j+1], dp[i+1][j])
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

ans = ""

def LCS(i=n,j=m):
    global ans
    if (i, j) == (0,0):
        return
    tmp = dp[i][j]
    if s[i-1] == t[j-1]:
        if i-1 >= 0 and j-1 >=0 and tmp == dp[i-1][j-1] + 1:
            ans = s[i-1] + ans
            LCS(i-1, j-1)
        elif i-1 >= 0 and tmp == dp[i-1][j]:
            LCS(i-1, j)
        elif j-1 >= 0 and tmp == dp[i][j-1]:
            LCS(i, j-1)
    else:
        if i-1 >= 0 and tmp == dp[i-1][j]:
            LCS(i-1, j)
        elif j-1 >= 0 and tmp == dp[i][j-1]:
            LCS(i, j-1)

LCS()
print(ans)

Solution (Python):
s = input()
t = input()

ls, lt = len(s), len(t)

dp = [[0]*(lt+1) for _ in range(ls+1)]
for i in range(1, ls+1):
    for j in range(1, lt+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1)
        dp[i][j] = max(dp[i][j], dp[i][j-1])
        dp[i][j] = max(dp[i][j], dp[i-1][j])

ans = ''
while ls > 0 and lt > 0:
    if dp[ls][lt] == dp[ls-1][lt]:
        ls -= 1
    elif dp[ls][lt] == dp[ls][lt-1]:
        lt -= 1
    else:
        ans = t[lt-1] + ans
        ls -= 1
        lt -= 1

print(ans)

Solution (Python):
s = input()
t = input()

dp = [[0]*(len(t)+1) for i in range(len(s)+1)]

for i in range(len(s)):
  for j in range(len(t)):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j]+1
    else:    
      dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
           
ans = ""
i = len(s)
j = len(t)
while i > 0 and j > 0 :
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] +ans
        i -= 1
        j -= 1
print(ans)

Solution (Python):
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)

s = input()
t = input()

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
ans = ''

for i in range(len(s) + 1):
	for j in range(len(t) + 1):
		if i == 0 or j == 0:
			dp[i][j] = 0
		elif s[i - 1] == t[j - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

i = len(s)
j = len(t)

while i > 0 and j > 0:
	if dp[i][j] > dp[i - 1][j] and dp[i][j] > dp[i][j - 1]:
		ans = s[i - 1] + ans
		i -= 1
		j -= 1
	elif dp[i][j] > dp[i - 1][j]:
		j -= 1
	else:
		i -= 1
		
print(ans)

Solution (Python):
s = input()
t = input()

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

for n in range(len(s)):
    for m in range(len(t)):
        if s[n] == t[m]:
            dp[n+1][m+1] = dp[n][m]+1
        else:
            dp[n+1][m+1] = max(dp[n+1][m],dp[n][m+1])

n = len(s)
m = len(t)
ans = ''
while n >= 0 and m >= 0:
    if dp[n][m] == dp[n-1][m]:
        n -= 1
    elif dp[n][m] == dp[n][m-1]:
        m -= 1
    else:
        ans = s[n-1]+ans
        n -= 1
        m -= 1
print(ans)