---
# System prepended metadata

title: Python題目解題

---

1. * # Python題目解題
#  hello :100: :memo:

## BST 二元搜尋樹
:::spoiler
```python=1
class tree: #二元樹宣告
    def __init__(self):
        self.data=0
        self.left=None
        self.right=None

def create_tree(root, val): #建立二元樹函數
    newnode=tree()
    newnode.data=val
    newnode.left=None
    newnode.right=None
    if root==None:
        root=newnode
        return root
    else:
        current=root
        while current!=None:
            backup=current
            if current.data>val:
                current=current.left
            else:
                current=current.right
        if backup.data>val:
            backup.left=newnode
        else:
            backup.right=newnode
    return root

def inorder(ptr): #中序走訪
    if ptr!=None:
        inorder(ptr.left)
        print(ptr.data)
        inorder(ptr.right)

def postorder(ptr): #後序走訪
    if ptr!=None:
        postorder(ptr.left)
        postorder(ptr.right)
        print(ptr.data)

def preorder(ptr): #前序走訪
    if ptr!=None:
        print(ptr.data)
        preorder(ptr.left)
        preorder(ptr.right)

def search(ptr, val): #二元樹搜尋
    while 1:
        if ptr==None:
            return None
        if ptr.data==val:
            return ptr
        elif ptr.data>val:
            ptr=ptr.left
        else:
            ptr=ptr.right
```
:::
## DP動態規劃
#### 最長遞增子序列
:::spoiler
```python=1
while 1:
    try:
        s=list(map(int,input().split()))
        m=[1 for i in range(0,len(s))]
        for i in range(0,len(s)):
            for j in range(0,i):
                if s[j]<s[i]:
                    if m[j]+1>m[i]:
                        m[i]=m[j]+1
        print(max(m))
    except:
        break
```
:::

#### 切棍子
:::spoiler
```python=1
v=[0,1,5,8,9,10,12,17,20,24,25]
dp=[0]*11

for i in range(1, 11):
    dp[i]=0
    for j in range(1, i+1):
        if dp[i-j]+v[j] > dp[i]:
            dp[i]=dp[i-j]+v[j]

n=int(input())
print(dp[n])
```
:::

#### b589
:::spoiler
```python=1
dp1=[0 for i in range(100)]
while 1:
    n=int(input())
    if n==0:
        break
    x=list(map(int, input().split()))
    dp=dp1.copy()
    for i in range(0,n):
        dp[i+1]=max(dp[i+1], dp[i]+x[i])
        dp[i+2]=max(dp[i+2], dp[i]+2*x[i])
    print(max(dp[n],dp[n+1]))
```
:::

#### 方格棋盤
:::spoiler
```python=1
#方格棋盤路線
#從左上角走到右下角的最大總和
#只能往右或往下
#最後一格一定是從dp[i-1][j] or dp[i][j-1]走過來的

m,n=map(int, input().split())
g=[]
for _ in range(m):
    g.append(list(map(int, input().split())))
dp=[[0 for i in range(n)] for j in range(m)]

dp[0][0]=g[0][0]
for i in range(1,m):
    dp[i][0]=dp[i-1][0]+g[i][0]

for i in range(1,n):
    dp[0][i]=dp[0][i-1]+g[0][i]

for i in range(1,m):
    for j in range(1,n):
        dp[i][j]=max(dp[i-1][j], dp[i][j-1])+g[i][j]

print(dp[-1][-1])

#input1
#3 4
#2 -2 3 3
#-6 5 2 -8
#3 7 -5 4

#input2
#2 5
#1 2 3 1 -5
#-2 5 -8 2 1

#output1
#11

#output2
#10
```
:::

#### 小朋友上樓梯
:::spoiler
```python=1
#小朋友上樓梯最小成本
#DP
#一次只能走一階或兩階
#最後一步一定是一階或是兩階 #c[i-1] or c[i-2]

n=int(input())
c=list(map(int, input().split()))
for i in range(2,n):
    c[i]=c[i]+min(c[i-1],c[i-2])
print(c[-1])

#input1
#8
#2 1 1 7 3 2 9 2

#input2
#5
#1 2 3 1 5

#output1
#9

#output2
#8

```
:::

#### 不連續的表演酬勞
:::spoiler
```python=1
#第一行為正整數n，第二行為n個正整數，代表每一天的酬勞
#限制:不能連續兩天表演
#選或不選

n=int(input())
p=list(map(int, input().split()))
dp=[0 for i in range(n)]
dp[0]=p[0]
dp[1]=max(dp[0], dp[1])
for i in range(2, n):
    dp[i]=max(p[i]+dp[i-2], dp[i-1])
    #如果選, 前一天就不能選-> p[i]+dp[i-2]
    #如果沒選, 酬勞就是前一天->dp[i-1]
print(dp[n-1])


#input1
#5
#1 2 3 1 5

#input2
#8
#2 1 1 7 3 2 9 2

#output1
#9

#output2
#18
```
:::

# :memo: 正式試題
## 103
#### 103 撲克牌
:::spoiler
```python=1
from itertools import combinations #組合

for _ in range(int(input())):
    ans=[]
    s=list(map(int, input().split()))
    data=list(combinations(s, 5)) #從6張卡片中取出5張
    for card_type in data:
        score=[] #5張牌的分數
        suit=[] #花色--> 0黑桃 1紅心 2方塊 3梅花
        point=[] #牌的點數
        cnt=[] #計算每種點數共有幾張
        for i in card_type:
            suit.append((i-1)//13)
            point.append((i-1)%13 if i%13!=0 else 13) #點數13因為取餘數剛好會等於0, 所以+13

        for i in set(point): #計算點數的張數
            cnt.append(point.count(i))

        cnt.sort() #cnt要做排序, 因為[1, 4] != [4, 1]

        min_card=min(card_type) #5張牌中最小的點數
        point=sorted(point)
        if point==[1, 2, 3, 4, 5] or point==[1, 10, 11, 12, 13]: #先處理順子的特殊情況
            if len(set(suit))==1: #看所有牌是否為相同的花色
                score.append(7)
            else:
                score.append(4)

        elif point==[i for i in range(min_card, min_card+5)]: #順子的一般情況
            if len(set(suit))==1:
                score.append(7)
            else:
                score.append(4)
        
        elif cnt==[1, 4]: #四張相同的牌-->四條
            score.append(6)
        elif cnt==[2, 3]: #三張相同的牌+兩張相同的牌-->葫蘆
            score.append(5)
        elif cnt==[1, 1, 3]: #三張相同的牌-->三條
            score.append(3)
        elif cnt==[1, 2, 2]: #兩張相同的牌+兩張相同的牌-->二條
            score.append(2)
        elif cnt==[1, 1, 1, 2]: #兩張相同的牌-->一條
            score.append(1)
        else:
            score.append(0) #雜牌

        ans.append(max(score))

    print(max(ans))
```
:::

#### 103 樹的某節點到根節點的距離
:::spoiler
```python=1
n=int(input())
for _ in range(n):
    a,b,c=map(int, input().split(','))
    path=[[] for i in range(a)]
    for i in range(a):
        s=list(map(int, input().split()))
        path[s[0]]=s[1:]
    
    ans=[]
    for i in range(b):
        node=path[c][i]
        cnt=0
        while node!=999:
            node=path[node][i]
            cnt+=1
        ans.append(cnt)
    
    for i in ans[:-1]:
        print(i, end=',')
    print(ans[-1])
```
:::

## 104
#### 104 矩陣的乘法
:::spoiler
```python=1
for _ in range(int(input())):
    a,b,c,d=map(int, input().split(','))
    A=[]
    B=[]
    AB=[]
    for i in range(a):
        A.append(list(map(int, input().split())))
    for i in range(c):
        B.append(list(map(int, input().split())))
    for i in range(a):
        AB.append(list(map(int, input().split())))
    
    INF=100000000
    ty=INF
    for i in range(a):
        if 9999 in A[i]:
            idxA=A[i].index(9999)
            for k in range(d):
                if B[idxA][k]!=0:
                    sum=0
                    for j in range(b):
                        if A[i][j]==9999:
                            e=B[j][k]
                        else:
                            sum+=A[i][j]*B[j][k]
                    ty=(AB[i][k]-sum)/e
                    
            if ty!=INF:
                break
    if ty==INF:
        rB=[]
        for i in range(d):
            rB.append([])
            for j in range(c):
                rB[i].append(B[j][i])
        #print(rB)
        for i in range(len(rB)):
            if 9999 in rB[i]:
                t=rB[i].index(9999)
                for k in range(a):
                    if A[k][t]!=0:
                        cnt=0
                        sum=0
                        for l in range(b):
                            if rB[i][l]==9999:
                                cnt=A[k][l]
                            else:
                                sum+=A[k][l]*rB[i][l]
                    ty=(AB[k][i]-sum)/cnt
                    if ty!=INF:
                        break
            if ty!=INF:
                break
    print(int(ty))
    #for i in B:
    #    print(i)
    #print('---')
    #for i in rB:
    #   print(i) 
```
:::


#### 104 最小成本生成樹
:::spoiler
```python=1
for _ in range(int(input())):
    parent=[int(i) for i in range(10)]
    s=input().split()
    data=[]
    for i in s:
        i=i.split(',')
        data.append((ord(i[0])-65,ord(i[1])-65,int(i[2])))
    data=sorted(data, key=lambda x:x[2])

    cost=0
    for i in data:
        a,b,c=i[0],i[1],i[2]
        if parent[a]==parent[b]:
            continue
        cost+=c
        mn=min(parent[a],parent[b])
        mx=max(parent[a],parent[b])
        for j in range(len(parent)):
            if parent[j]==parent[mn]:
                parent[j]=parent[mx]
    print(cost)
```
:::

## 105
#### 105E 是否為heap tree or binary search tree
:::spoiler
```python=1
for _ in range(int(input())):
    tree=list(map(int, input().split(',')))
    maxnode=len(tree)-1
    max_heap=True
    min_heap=True
    bin_search=True

    for i in range(len(tree)):
        num=[]
        num.append(tree[i])
        if i*2+1<=maxnode:
            num.append(tree[i*2+1])
        if i*2+2<=maxnode:
            num.append(tree[i*2+2])

        if len(num)==1:
            continue
        if len(num)==2:
            if num[0]>num[1]:
                min_heap=False
            if num[0]<num[1]:
                max_heap=False
                bin_search=False
        if len(num)==3:
            if num[0]>num[1] or num[0]>num[2]:
                min_heap=False
            if num[0]<num[1] or num[0]<num[2]:
                max_heap=False
            if num[0]<num[1] or num[0]>num[2]:
                bin_search=False
    
    if min_heap or max_heap:
        print('H')
    elif bin_search:
        print('B')
    else:
        print('F')
```
:::

#### 105F 後序表示法
:::spoiler
```python=1
def f(n,ls,rs):
    global prefix, infix
    postfix=[]
    if ls==rs:
        return [prefix[n]]
    if ls>rs:
        return []
    pos=infix.index(prefix[n])

    N=[prefix[n]]
    L=f(n+1,ls,pos-1)
    R=f(n+(pos-ls)+1,pos+1,rs)
    
    if R==None:
        R=[]
    if L==None:
        L=[]
    for i in L:
        postfix.append(i)
    for i in R:
        postfix.append(i)
    for i in N:
        postfix.append(i)
    return postfix

for _ in range(int(input())):
    infix=input().replace(' ','').split(',')
    prefix=input().replace(' ','').split(',')
    ans=f(0,0,len(prefix)-1)
    print(','.join(ans))
```
:::

#### 105G 兩字串LCS
:::spoiler
```python=1
for _ in range(int(input())):
    a='0'+input()
    b='0'+input()
    dp=[[0 for i in range(len(b))] for j in range(len(a))]
    for i in range(1,len(a)):
        for j in range(1,len(b)):
            if a[i]==b[j]:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=max(dp[i-1][j], dp[i][j-1])
    print(dp[-1][-1])
```
:::

#### 105H 霍夫曼編碼
:::spoiler
```python=1
# 解法一

n=int(input())
tree=[]
#樹深度追蹤
def tree_lv(node,lv):
    global tree
    node[2]=lv
    if node[3]>=0:
        tree_lv(tree[node[3]],lv+1) #左兒子
    if node[4]>=0:
        tree_lv(tree[node[4]],lv+1) #右兒子

for i in range(0,n):
    x=list(map(int, input().split(',')))
    node=[]
    for a in range(0,len(x)):
        node.append([a,x[a],0,-1,-1])
    node=sorted(node, key=lambda x:x[1])
    tree=[]
    num=len(node)
    mx_num=num

    #建樹, num>=len(tree) 為中繼點
    while len(node)>1:
        a=node[0]
        b=node[1]
        c=[num,a[1]+b[1],0,a[0],b[0]] #合併為中繼點
        num+=1
        tree.append(a)
        tree.append(b)
        node[1]=c
        node.remove(a)
        node=sorted(node,key=lambda x:x[1])
    
    tree.append(node[0])
    tree=sorted(tree,key=lambda x:x[0])
    #print(tree)
    tree_lv(node[-1],0)
    #print(tree)
    for i in range(0,mx_num-1):
        print(tree[i][2], end=',')
    print(tree[mx_num-1][2])
```
:::
    
:::spoiler
```python=1
# 解法二
for _ in range(int(input())):
    s=list(map(int, input().split(",")))
    n=l=len(s)
    tree=[]
    for i in range(l):
        tree.append((i, s[i])) # 編號, 次數

    result=[]
    parent=[None]*l

    while len(tree)>1:
        tree.sort(key=lambda x:x[1])
        a=tree.pop(0)
        b=tree.pop(0)
        newnode=a[1]+b[1]
        tree.append((l, newnode))
        parent.append(None)
        parent[a[0]]=l
        parent[b[0]]=l
        l+=1

    for i in range(n):
        cu=parent[i]
        cnt=0
        while cu!=None:
            cu=parent[cu]
            cnt+=1
        result.append(cnt)

    print(*result, sep=",")

```
:::

## 106
#### 106B 羅馬數字轉整數
:::spoiler
```python=1
num={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
def g(key):
    pre=None
    sum=0
    for i in range(len(key)):
        sum+=num[key[i]]
        if (key[i]=='X' or key[i]=='V') and pre=='I':
            sum-=2
        if (key[i]=='L' or key[i]=='C') and pre=='X':
            sum-=20
        if (key[i]=='M' or key[i]=='D') and pre=='C':
            sum-=200
        pre=key[i]
    return sum

for _ in range(int(input())):
    key=input().strip()
    print(g(key))
```
:::

#### 106G 樹
:::spoiler
```python=1
"""
這題跟zerojudge b517是否為樹類似
我的想法是先判斷這張圖是不是樹，不是樹的話，再去看他有沒有形成迴圈
要符合樹的條件有以下兩點：
1. 節點(node)-1 == 邊(edge) 的數量
2. DFS拜訪完的節點數量 == 輸入時出現過的節點數量
"""

def dfs(x, px): #判斷是否為樹函式
    visited.append(x)
    for i in range(20):
        if path[x][i]==1 and i!=px and i not in visited:
            dfs(i, x)

def Cycle(x, px): #尋找形成迴圈的所有節點
    global start
    visited_cyc.append(x)
    for i in range(20):
        if path[x][i]==1 and i==start and i!=px and i in visited_cyc:
            visited_cyc.append(i)
        if path[x][i]==1 and i!=px and i not in visited_cyc:
            Cycle(i, x)
            
for _ in range(int(input())):
    s=input().split()
    path=[[0 for _ in range(20)] for _ in range(20)]
    node=[0]*20 #紀錄出現過的節點
    edge=0 #紀錄邊的數量
    root=None
    for i in s:
        a, b=map(int, i.split(","))
        if root==None:
            root=a
    
        path[a][b]=1; path[b][a]=1
        node[a]=1; node[b]=1
        edge+=1
    
    node_num=node.count(1) #設為1的即為出現過的節點
    is_tree=True #是否為樹
    visited=[]
    dfs(root, root)
    
    #這邊用來判斷符不符合樹的條件
    if node_num-1!=edge or len(visited)!=node_num:
        is_tree=False
    
    #如果是樹就直接輸出T
    if is_tree:
        print("T")
    else:
        cycle=[]
        """
        如果visited==node_num，代表符合第二點條件，
        那就不可能是森林，所以必定有形成迴圈的情況。
        """
        if len(visited)==node_num:
            for i in range(20):
                if node[i]==1:
                    start=i #紀錄第一個走訪的節點
                    visited_cyc=[]
                    Cycle(i, i)
                    #如果重複走到第一個節點，代表此節點是迴圈節點之一
                    if visited_cyc.count(i)>1:
                        cycle.append(i)
            print(*cycle, sep=", ")
        
        #否則就是森林，直接輸出F
        else:
            print("F")
```
:::

## 107
#### 107B 井字棋
:::spoiler
```python=1
for x in range(int(input())):
    lst=[]
    for i in range(3):
        lst.append(list(input().strip()))

    player=[0]*3
    for i in range(3):
        if len(set(lst[i]))==1 and lst[i][0]!='0':
            player[int(lst[i][0])]+=1
    
    for i in range(3):
        num=[]
        for j in range(3):
            num.append(int(lst[j][i]))
        if len(set(num))==1 and num[0]!=0:
            player[num[0]]+=1
    
    if lst[0][0]==lst[1][1]==lst[2][2] and lst[0][0]!='0':
        player[int(lst[0][0])]+=1
    if lst[0][2]==lst[1][1]==lst[2][0] and lst[0][2]!='0':
        player[int(lst[0][2])]+=1

    mx=max(player)
    if mx==0:
        print(3)
    else:
        print(player.index(mx))
```
:::

#### 107G 找兩節點之間的最長路徑
:::spoiler
```python=1
def dfs(x):
    if x>=l:
        return -1
    if tree[x]=="null":
        return -1
    return max(dfs(x*2+1)+1, dfs(x*2+2)+1)

for _ in range(int(input())):
    tree=input()[1:-1].split(",")
    l=len(tree)
    ans=0
    for i in range(l):
        tmp=2+dfs(i*2+1)+dfs(i*2+2)
        if tmp>ans:
            ans=tmp
    print(ans)
```
:::

#### 107H 循環排列
:::spoiler
```python=1
for _ in range(int(input())):
    s=input().replace('[','').replace(']','').split(',')
    ans=[]
    visited=[]
    for i in range(len(s)):
        cyc=[]
        idx=i+1
        if idx not in visited:
            while idx not in cyc:
                visited.append(idx)
                cyc.append(idx)
                idx=int(s[idx-1])
            if cyc!=[]:
                ans.append(cyc)
    print(ans)
```
:::

## 108
#### 108B 保齡球計分
:::spoiler
```python=1
for _ in range(int(input())):
    data=[]
    s=input().split()
    for i in s:
        if i=='X':
            data.append(10)
        elif i=='/':
            data.append(10-data[-1])
        else:
            data.append(int(i))

    total=0
    cnt=0
    while len(data)>0:
        cnt+=1
        score=0
        a=data.pop(0)
        if a==10:
            score+=a+data[0]+data[1]
            if cnt==10:
                data.pop(0)
                data.pop(0)
        else:
            if len(data)==0:
                break
            b=data.pop(0)
            if a+b==10:
                if cnt!=10:
                    score+=a+b+data[0]
                else:
                    score+=a+b+data[0]
                    data.pop(0)
            else:
                score+=a+b
        total+=score
    print(total)
```
:::


#### 108F 循環小數
:::spoiler
```python=1
for _ in range(int(input())):
    a,b=map(int, input().split())
    q=str(a//b)+'.'
    a=a%b
    r=[]
    r.append(a)
    s1=''
    round=''
    while a>0:
        a*=10
        s1+=str(a//b)
        a=a%b
        if a in r:
            c=r.index(a)
            round=s1[0:c]+'('+s1[c:]+')'
            break
        else:
            r.append(a)
        
        if len(s1)>=50:
            round+='('+s1+'...)'
            break
    
    if len(round)==0:
        print(q+s1+'(0)')
    else:
        print(q+round)
```
:::

#### 108G 著色問題
:::spoiler
```python=1
n=int(input())
while n!=0:
    m=int(input())
    color=[-1 for i in range(n)]
    f=True
    for i in range(m):
        a,b=map(int, input().split())
        if color[a]==-1 and color[b]==-1:
            color[a]=True
            color[b]=False
        elif color[a]==color[b]:
            f=False
        elif color[a]==-1:
            color[a]=not(color[b])
        else:
            color[b]=not(color[a])
    print('BICOLORABLE.' if f else 'NOT BICOLORABLE.')
    n=int(input())
```
:::

#### 108H 數字迷宮
:::spoiler
```python=1
from heapq import *

for _ in range(int(input())):
    n=int(input())
    m=int(input())
    g=[]
    for _ in range(n):
        g.append(list(map(int, input().split())))
    
    visited=[[False for i in range(m)] for j in range(n)]
    dxy=((0,1),(1,0),(-1,0),(0,-1))
    visited[0][0]=True
    q=[(g[0][0],0,0)]

    while q:
        val,r,c=heappop(q)
        val=abs(val)
        for i in range(4):
            newr=r+dxy[i][0]
            newc=c+dxy[i][1]
            if 0<=newr<n and 0<=newc<m and not visited[newr][newc]:
                visited[newr][newc]=True
                g[newr][newc]=val+g[newr][newc]
                heappush(q, (g[newr][newc], newr,newc))
    print(g[-1][-1])
```
:::

## 109
#### 109B 打印機
:::spoiler
```python=1
for _ in range(int(input())):
    n=list(input().strip())
    num=''
    for i in range(len(n)):
        if int(n[i])==4:
            n[i]='3'
            num+='1'
        else:
            num+='0'
    print(''.join(n), int(num))
```
:::

#### 109F 最大子數列問題(最大連續和)
:::spoiler
```python=1
for _ in range(int(input())):
    mx=-1e9
    s=list(map(int, input().split()))
    sum=0
    for i in s:
        sum+=i
        mx=max(sum, mx)
        if sum<0:
            sum=0
    print(mx)
```
:::

#### 109G 錄音帶(背包問題)
:::spoiler
```python=1
def f(w,v):
    for i in range(1,T+1):
        for j in range(1,N+1):
            if j>=w[i]:
                dp[i][j]=max(dp[i-1][j-w[i]]+v[i], dp[i-1][j])
            else:
                dp[i][j]=dp[i-1][j]
    return dp[-1][-1]

while 1:
    try:
        s=list(map(int, input().split()))
        N=s[0]
        T=s[1]
        w=[0]+s[2:]
        v=[0]+s[2:]
        dp=[[0 for i in range(N+1)] for j in range(T+1)]
        ans=f(w,v)
        print(ans)
    except:
        break
```
:::

#### 109H 特殊郵件
:::spoiler
```python=1
for _ in range(int(input())):
    n=int(input())
    path=[0 for i in range(n+1)]
    for i in range(n):
        a,b=map(int, input().split())
        path[a]=b

    visited1=[0 for i in range(n+1)]
    max_cost=0
    for i in range(1,n+1):
        visited=visited1.copy()
        visited[i]=visited[0]=1
        nxt=path[i]
        cnt=0

        while visited[nxt]==0:
            cnt+=1
            visited[nxt]=1
            nxt=path[nxt]
        
        if cnt>max_cost:
            max_cost=cnt
            ans=i
    print(ans)
```
:::
## 110
#### 110M 矩陣的直積
:::spoiler
```python=1
a,b,c,d=map(int, input().split())
AB=[]
A=[]
B=[]
for _ in range(a):
    A.append(list(map(int, input().split())))
for _ in range(c):
    B.append(list(map(int, input().split())))

r=0
for i in range(a):
    for j in range(c):
        AB.append([])
        for k in range(b):
            for l in range(d):
                AB[r].append(A[i][k]*(B[j][l]))
        r+=1

for i in AB:
    print(*i)
```
:::

#### 110N 字串編輯距離
:::spoiler
```python=1
a='0'+input()
b='0'+input()
dp=[[0 for i in range(len(b))] for i in range(len(a))]

for i in range(1,len(a)):
    dp[i][0]=i

for i in range(1,len(b)):
    dp[0][i]=i

for i in range(1,len(a)):
    for j in range(1,len(b)):
        if a[i]==b[j]:
            dp[i][j]=dp[i-1][j-1]
        else:
            dp[i][j]=min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1

print(dp[-1][-1])
```
:::

#### 110O 三字串LCS
:::spoiler
```python=1
a='0'+input()
b='0'+input()
c='0'+input()
dp=[[[0 for i in range(len(c))] for i in range(len(b))] for i in range(len(a))]
for i in range(1,len(a)):
    for j in range(1,len(b)):
        for k in range(1,len(c)):
            if a[i]==b[j]==c[k]:
                dp[i][j][k]=dp[i-1][j-1][k-1]+1
            else:
                dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k],dp[i][j][k-1])
print(dp[-1][-1][-1])
```
:::

#### 110P 錢幣
:::spoiler
```python=1
n=int(input())
s=list(map(int, input().split()))
can=[False]*100001
max_v=sum(s)
can[0]=True
for i in range(n):
    for j in range(max_v,s[i]-1,-1):
        can[j]|=can[j-s[i]]
        
ans=[]
for i in range(1, max_v+1):
    if can[i]:
        ans.append(i)
print(len(ans))
print(*ans)
```
:::

#### 110Q 果子堆合併
:::spoiler
```python=1
while 1:
    try:
        n=int(input())
        s=list(map(int, input().split()))
        s.sort()
        sum=0
        for i in range(n-1):
            a=s.pop(0)
            b=s.pop(0)
            sum+=a+b
            s.append(a+b)
            s.sort()
        print(sum)
    except:
        break
```
:::

#### 110R 條條大路通羅馬
:::spoiler
```python=1
n,m=map(int, input().split())
path=[[] for i in range(n+1)]
for _ in range(m):
    a,b=map(int, input().split())
    path[a].append(b)

visited=[0 for i in range(n+1)]
def dfs(x):
    visited[x]=1
    for i in path[x]:
        if visited[i]==0:
            dfs(i)
a,b=map(int, input().split())
dfs(a)
if visited[b]==1:
    print('Yes')
else:
    print('No')
```
:::

## 111模擬
#### 111E1 二元樹
:::spoiler
```python=1
while 1:
    try:
        dic={}
        f=False; Tree=True
        while 1:
            s=input().split()
            for i in s:
                if i=='()':
                    f=True
                else:
                    a,b=i[1:len(i)-1].split(',')
                    if b=='':
                        b='root'
                    if b in dic:
                        Tree=False
                    dic[b]=a
            if f:
                break

        if 'root' not in dic:
            Tree=False
        if Tree:
            tree=[]
            tree.append(dic['root'])
            del dic['root']
            q=['L','R']
            while q:
                node=q.pop(0)
                if node in dic:
                    tree.append(dic[node])
                    q.append(node+'L')
                    q.append(node+'R')
                    del dic[node]

        if len(dic)>0:
            print('not complete')
        elif not Tree:
            print('not complete')
        else:
            print(*tree)
    except:
        break
```
:::

#### 111E2 迷宮
:::spoiler
```python=1
import heapq

for _ in range(int(input())):
    n=int(input())
    m=int(input())
    G=[]
    for i in range(n):
        s=list(map(int, input().split()))
        G.append(s)
    v=[[False for i in range(m)] for i in range(n)]
    dx=(0,0,1,-1)
    dy=(1,-1,0,0)
    queue=[(G[0][0],0,0)]
    while queue!=[]:
        pair=heapq.heappop(queue)
        num=pair[0]
        y=pair[1]
        x=pair[2]
        for i in range(4):
            r=dy[i]+y
            c=dx[i]+x
            if r<0 or c<0 or r>n-1 or c>m-1 or v[r][c]:
                continue
            G[r][c]=num+G[r][c]
            v[r][c]=True
            heapq.heappush(queue, (G[r][c],r,c))

    print(G[-1][-1])
```
:::

#### 111T 路徑
:::spoiler
```python=1
def dfs(x,path):
    path.append(tree[x])
    r=0
    if x*2+1<=max_node and tree[x*2+1]!='null':
        r+=1
        dfs(x*2+1, path.copy())
    if x*2+2<=max_node and tree[x*2+2]!='null':
        dfs(x*2+2, path.copy())
        r+=1
    if r==0:
        ans.append(path)
        
tree=input().split(',')
max_node=len(tree)-1
ans=[]
dfs(0,[])
for i in ans:
    print(*i,sep='->')

```
:::

## 111
#### 111G 編碼
:::spoiler
```python=1
for _ in range(int(input())):
    s=input()
    alpha=[]
    num=[]
    number=''
    for i in range(len(s)):
        if s[i].isalpha():
            alpha.append(s[i])
            if number!='':
                num.append(int(number))
                number=''
        else:
            number+=s[i]

    if number!='':
        num.append(int(number))
    
    for i in range(len(num)):
        print(alpha[i]*num[i], end='')
    print()
```
:::

#### 111H 分組反轉字串
:::spoiler
```python=1
while 1:
    s=input().split()
    if s[0]=='0':
        break
    group=int(s[0])
    data=s[1]
    
    num=int(len(data)/group)
    str1=''
    ans=''
    for i in range(len(data)):
        str1+=data[i]
        if (i+1)%num==0:
            ans+=str1[::-1]
            str1=''
    print(ans)
```
:::

#### 111I 字元出現字數
:::spoiler
```python=1
data=[]
s=input().strip()
s1=list(set(s))
for i in s1:
    data.append((ord(i), s.count(i)))

data.sort(key=lambda x:(x[1], -x[0]))
for i in data:
    print(*i)
```
:::

#### 111J 質數
:::spoiler
```python=1
def f(n):
    if n<2:
        return False
    for i in range(2, int(n**0.5)+1):
        if n%i==0:
            return False
    return True

for aa in range(int(input())):
    if aa>0:
        print()
    m,n=map(int, input().split())
    for i in range(m, n+1):
        if f(i):
            print(i)
```
:::

#### 111K 質因數
:::spoiler
```python=1
def f(n):
    k=0
    for i in range(2, int(n**0.5)+1):
        if n%i==0:
            k=i
            break
    if k!=0:
        num.append(k)
        f(n//k)
    else:
        num.append(n)

while 1:
    n=int(input())
    if n==0:
        break
    if n==1:
        print('1 : 0')
        continue
    num=[]
    f(n)
    num=set(num)
    print('%d : %d'%(n,len(num)))
```
:::

#### 111M 格雷碼
:::spoiler
```python=1
n=int(input())
g=['0','1']
for i in range(1, n):
    a=[]
    b=[]
    for j in g:
        a.append('0'+j)
    g=g[::-1]
    for j in g:
        b.append('1'+j)
    g=a+b

for i in g:
    print(i)
```
:::

#### 111Q 二元樹資訊
:::spoiler
```python=1
def height(l, r):
    left=0
    right=0
    if l!=-1:
        left=height(Node[l][0],Node[l][1])+1
    if r!=-1:
        right=height(Node[r][0],Node[r][1])+1
    return max(left, right)

def depth(n, cnt_d):
    d[n]=cnt_d
    for i in Node[n]:
        if i!=-1:
            depth(i, cnt_d+1)            

n=int(input())
Node=[]
parent=[-1]*n
deg=[]
h=[]
d=[None]*n

for i in range(n):
    node, l, r=map(int, input().split())
    Node.append((l, r))
#計算子節點數量、尋找父節點
for i in range(n):
    cnt_deg=0
    for j in Node[i]:
        if j!=-1:
            cnt_deg+=1
            parent[j]=i
    deg.append(cnt_deg)
#計算深度
root=parent.index(-1)
depth(root, 0)
#計算高度、輸出
for i in range(n):
    h.append(height(Node[i][0],Node[i][1]))
    print('node %d: parent = %d, degree = %d, depth = %d, height = %d,'\
          %(i, parent[i], deg[i], d[i], h[i]))
```
:::

## 112
#### 112J 七段顯示器
:::spoiler
```python=1
for _ in range(int(input())):
    n=int(input())
    mod=n%2
    if mod==0:
        a="1"
        n-=2
    else:
        a="7"
        n-=3

    b=(n//2)*"1"    
    print(a+b) 
```
:::

#### 112K 字串
:::spoiler
```python=1
for _ in range(int(input())):
    n=int(input())
    ans=set()
    s=list(input())

    for i in range(len(s)-1):
        s1=s.copy()
        for j in range(i, i+2):
            s1[j]=""
        rst="".join(s1)
        ans.add(rst)

    print(len(ans))
```
:::

#### 112P 魔術方陣
:::spoiler
```python=1
arr=[]
for _ in range(3):
    arr.append(list(map(int, input().split())))

a=arr[1][0]+arr[2][0]
b=arr[0][1]+arr[2][1]
c=arr[2][0]+arr[2][1]

total=(a+b+c)//2

arr[0][0]=total-a
arr[1][1]=total-b
arr[2][2]=total-c

for i in arr:
    print(*i)
```
:::

#### 112R 樹的直徑
:::spoiler
```python=1
#直接窮舉每個節點到其他節點的距離#
def dfs(x, cnt):
    visited[x]=1
    distance[x]=cnt
    for i in path[x]:
        if visited[i]==0:
            dfs(i, cnt+1)

n=int(input())
path=[[] for _ in range(n+1)]
for _ in range(n-1):
    a, b=map(int, input().split())
    path[a].append(b)
    path[b].append(a)

rst=[]
for i in range(1, n+1):
    visited=[0]*(n+1)
    distance=[0]*(n+1)
    dfs(i, 0)
    rst.append(max(distance))

print(max(rst))
```
:::

#### 112S 迴圈
:::spoiler
```python=1
def dfs(x):
    visited[x]=1
    v1.append(x)
    for i in path[x]:
        if visited[i]==0:
            dfs(i)

n, m=map(int, input().split())
path=[[] for _ in range(n+1)]
node=[0]*(n+1)
visited=[0]*(n+1)
for _ in range(m):
    a, b=map(int, input().split())
    path[a].append(b)
    path[b].append(a)
    node[a]=1
    node[b]=1

ans=0
data=[]
for i in range(len(node)):
    if node[i]==1 and visited[i]==0:
        #print(i)
        v1=[]
        dfs(i)
        data.append(v1)

for i in data:
    for j in i:
        if len(path[j])!=2:
            #Hint 1.
            #循環圖(cycle graph)內所有節點的鄰居和連出的邊都等於2
            break
    else:
        ans+=1
        
print(ans)
```
:::

# 模擬試題
#### 104模擬3_1 是否為樹
:::spoiler
```python=1
for _ in range(int(input())):
    data=[]
    g={}
    node=set()
    edge=0
    s=input().split()
    for i in s:
        a,b=i.split(',')
        data.append((int(a),int(b)))
    
    for a,b in data:
        node.add(a)
        node.add(b)
        edge+=1
        if a not in g:
            g[a]=[b]
        else:
            g[a]+=[b]
        if b not in g:
            g[b]=[a]
        else:
            g[b]+=[a]
    
    Tree=True
    if edge!=len(node)-1:
        Tree=False
    
    if Tree:
        node=list(node)
        visited=[]
        def dfs(x):
            global Tree
            visited.append(x)
            for i in g[x]:
                if i not in visited:
                    dfs(i)
        dfs(node[0])
    
        if len(node)!=len(visited):
            Tree=False

    if Tree:
        print('T')
    else:
        print('F')
```
:::

#### 108旗立 尋找樹中最大路徑和
:::spoiler
```python=1
def dfs(n, path=[]):
    path.append(int(tree[n]))
    r=0
    if n*2+1<=max_node:
        if tree[n*2+1]!='null':
            dfs(n*2+1, path.copy())
            r+=1
    if n*2+2<=max_node:
        if tree[n*2+2]!='null':
            dfs(n*2+2, path.copy())
            r+=1
    if r==0: #到leaf了...
        lst.append(sum(path))

for _ in range(int(input())):
    tree=input().replace(' ','').replace('[','').replace(']','').split(',')
    max_node=len(tree)-1 #處理邊界,避免出現溢位
    ans=[]
    for i in range(len(tree)):
        if tree[i]=='null':
            continue
        lst=[]
        L=0
        R=0
        if i*2+1<=max_node and tree[i*2+1]!='null':
            dfs(i*2+1,[])
            if lst!=[]:
                L=max(max(lst),0) #如果max(lst)<0,那就不能走,不然路徑和會變小
                lst.clear() #清空
        if i*2+2<=max_node and tree[i*2+2]!='null':
            dfs(i*2+2,[])
            if lst!=[]:
                R=max(max(lst),0) #如果max(lst)<0,那就不能走,不然路徑和會變小
        ans.append(int(tree[i])+L+R)
    print(max(ans))


#input 1
#6
#[-23, -48, 41, 10, 3, -46, 8, -39, 31, 32, -26, 40, -35, -28, 6, 26, 37, 5, 20, 16, 22, 37, 10, 17, 27, -20, -18, -20, -18]
#[1, -26, -26, -6, -36, 6, 13, 18, -45, 26, 38, -47, -1, -42, 5, -17, 46, 40, 6, -33, -35, -49, -26, 24, -15]
#[12, -27, 23, -23, 29, -44, 31, 9, 15, 41, 29, -9, -30, -27, 37, 14, 40, 35, 34]
#[-30, 47, -14, -9, 27, 7, 36, 15, -50, 1, -42, 22, -18]
#[-23, -1, -42, 47, 18, -1, 40, -7, -33, -2, -14, 44, -22, -13, -16, 39, 1, -18, 15, 12, -23, -14, 37, -49, null, 46]
#[-33, 20, 20, 38, -6, -7, -19, -9, 26, 37, -8, -41, -19, 4, -31, 44, -9, 13, 7, -23, 16, 13, 8, -10, 18, -33, -33, 47, 12]

#input 2
#9
#[17, -40, -42, 3, 25, 19, -24, -28, 11, -40, -49, -32, -16, -24, -35, -41, 39, -20, -33, 39, 35]
#[21, 23, -33, 5, 48, 27, 43, 17, 40, -3, -8, 8, -48, 3, 48, -39, -23, 24, 47, 9, 8, -46, 14]
#[-26, -39, -25, 44, -2, 16, -2, -41, 19, -4, 31, 8, -36, -21, -5, 18, -7, -39, 22, 43, 19, -38, 6, 42, -32, 41, -36]
#[3, 8, -42, -14, -46, 3, 15, 18, 24, -9, 32, 44, -2, -16, -44, -34, 4, -37, -5, 1, 41, -36, 43, 43, 40, 32, -18, 5]
#[38, 1, 11, -47, 35, 39, 22, -28, -41, 26, 31, -50, 20, 21, 41, 50, -29]
#[26, 15, 28, 20, -14, -36, 20, 16, -34, -4, -27, -29, -40, -16, 49, 34, -20, -18, -6, -1, -32, -5, -18, -47, 20, 21]
#[-1]
#[-1,9,20,null,null,15,7]
#[-3,-2,-1]

#outout1
    #84
    #64
    #146
    #81
    #119
    #144

#output 2
    #39
    #194
    #85
    #127
    #179
    #208
    #-1
    #43
    #-1
```
:::

#### 109模擬 關節點
:::spoiler
```python=1
while 1:
    n=int(input())
    if n==0:
        break
    path=[[0 for i in range(n+1)] for j in range(n+1)]
    AP=[]
    while 1:
        x=list(map(int, input().split()))
        if x[0]==0:
            break
        for i in range(1,len(x)):
            path[x[0]][x[i]]=1
            path[x[i]][x[0]]=1
    
    visited1=[0 for i in range(n+1)]
    for i in range(1, n+1): #1~n+1-> 每一個節點
        visited=visited1.copy()
        BFS=[]
        pos=i%n+1
        BFS.append(pos)
        while BFS:
            pos=BFS.pop(0)
            visited[pos]=1
        
            for j in range(1,n+1):
                if j==i:
                    continue
                if visited[j]==0 and path[pos][j]==1:
                    BFS.append(j)
            
        for j in range(1,n+1):
            if visited[j]==0 and i!=j:
                AP.append(i)
                break

    print(len(AP))
```
:::