# APCS 2023/10/22 python題解

## 1. 機械鼠

https://zerojudge.tw/ShowProblem?problemid=m370

- 利用filter函數找出大於x的食物個數,再判斷往左或往右移動可以吃到更多食物

# 輸入x為老鼠起始位置,n為食物數量,l為食物位置  
x, n = map(int, input().split())
l = list(map(int, input().split()))

# 使用filter找出大於x的食物個數  
temp = len(list(filter(lambda i: i>x, l)))  

# 判斷往左或往右可以吃到更多食物
if temp > n // 2:
  print(temp, max(l)) # 往右吃更多  
else:
  print(n - temp, min(l)) # 往左吃更多

## 2. 卡牌遊戲

https://zerojudge.tw/ShowProblem?problemid=m371

- 記錄每個數字出現位置,判斷可以消除的組合並累加分數

from sys import stdin
e = stdin.readline

# 輸入表格大小 
m, n = map(int, e().split())

# 建立表格  
l = [list(map(int, e().split())) for _ in range(m)]

# 記錄每個數字出現位置
pos = {}  
for i in range(m):
  for j in range(n):
    k = l[i][j]
    if k not in pos:
      pos[k] = []
    if pos[k]:
      x, y = pos[k][0]
      # 判斷是否可以相互消除
      if i != x and j != y:  
        del pos[k]
        continue
    pos[k].append((i, j))
        
# 檢查每個數字的兩個位置是否可以相互消除  
# 如果可以就刪除位置記錄並累加分數
ans = 0
while True:
  for k in pos:
    s, t = pos[k]  
    a, b = s
    c, d = t
    if a == c:
      # 判斷中間是否有阻礙
      for i in range(b+1, d):
        if l[a][i] >= 0: break
      else:
        ans += k
        l[a][b] = -1
        l[c][d] = -1
        del pos[k]
        break
    else:
      for i in range(a+1, c):
        if l[i][b] >= 0: break
      else:
        ans += k
        l[a][b] = -1
        l[c][d] = -1
        del pos[k]
        break
  else: break
        
print(ans)

## 3. 搬家

https://zerojudge.tw/ShowProblem?problemid=m372

- DFS搜尋每個連通塊大小並記錄最大值

from sys import stdin
def e(): return stdin.readline().strip()

# 定義水管方向對應表
T = {"F":(0, 1, 0, 1),
     "H":(0, 0, 1, 1),
     "7":(0, 1, 1, 0),
     "I":(1, 1, 0, 0),
     "X":(1, 1, 1, 1),
     "L":(1, 0, 0, 1),
     "J":(1, 0, 1, 0),
     "0":(0, 0, 0, 0)
    }
     
m, n = map(int, e().split())
l = [list(e()+"0") for _ in range(m)] + [["0"]*n]

ans = 0
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# DFS搜尋每個連通塊 
for i in range(m):
  for j in range(n):
    if l[i][j] == "0": continue
    stack = [(i, j)]
    c = 0
    while stack:
      i, j = stack.pop()
      if l[i][j] == "0": continue
      t = T[l[i][j]]  
      l[i][j] = "0"
      c += 1
      for idx in range(4):
        if not t[idx]: continue  
        di, dj = d[idx]
        ni, nj = i + di, j + dj
        if T[l[ni][nj]][idx^1]:
          stack.append((ni, nj))
          
    # 記錄最大連通塊大小       
    ans = max(c, ans) 

print(ans)

## 4. 投資遊戲

https://zerojudge.tw/ShowProblem?problemid=m373

- 動態規劃計算使用每個金牌的最大收益

def main():
    from sys import stdin, stdout
    e = stdin.readline

    n, k = map(int, e().split())
    l = list(map(int, e().split()))

    # 建立dp table
    # dp[i][j] = 使用i個金牌,前j天的最大收益
    dp = [[0]*n for i in range(k+1)]
    for i in range(n):
        dp[0][i] = max(dp[0][i-1], 0) + l[i]

    for i in range(1, k+1):
        dp[i][0] = max(0, dp[i-1][0])
        for j in range(1, n):
            # dp轉移式
            dp[i][j] = max(dp[i][j-1] + l[j], dp[i-1][j-1])
    
    # 輸出使用所有金牌的最大收益 
    stdout.write(str(max(dp[-1]+[0])))
main()