#第一题

str = 'abc##dfg##gh'
for i in range(0,len(str)):
    if str[i]=='#':
        str = str[i]+str[0:i]+str[i+1:]
print(str)


#第二题
data =[[3,5,2,4],[3,6,2,3],[4,6,7,7]]
rows = len(data)
cols = len(data[0])
dp = [[0 for _ in range(cols)] for _ in range(rows)]
path = [[False for _ in range(cols)] for _ in range(rows)]

dp[0][0] = data[0][0]
for i in range(1,rows):
    dp[i][0] = data[i][0] + dp[i-1][0]
dp[0][0] = data[0][0]
for j in range(1,cols):
    dp[0][j] = data[0][j] + dp[0][j-1]

#print(dp)

for i in range(1,rows):
    for j in range(1,cols):
        #dp[i][j] = max(dp[i-1][j]+data[i][j] , dp[i][j-1]+data[i][j])
        if dp[i-1][j]+data[i][j] > dp[i][j-1]+data[i][j]:
            dp[i][j] = dp[i-1][j] + data[i][j]
            path[i][j] = 'up'
        else:
            dp[i][j] = dp[i][j-1]+data[i][j]
            path[i][j] = 'left'


print(dp)
print(path)

#第三题
tree = [0,1,2,3,4,5,6,-1,-1,9]
def findcommonnode(node1, node2):
    set1 = set()
    while (node1-1)/2 >= 0:
        node1 = int((node1-1) / 2)
        set1.add(node1)

    set2 = set()
    while (node2-1)/2 > 0:
        node2 = int((node2-1)/2)
        set2.add(node2)

    return max(set1.intersection(set2))


print(findcommonnode(4,3))