# pA. 單調陣列 ```python= while True: try: n = eval(input()) except: break if sorted(n) == n or sorted(n, reverse=True) == n: print('true') else: print('false') ``` # pB. 修課 拓樸排序 ```python= from collections import deque, defaultdict def sol(n, p, times): # 建立圖 g = defaultdict(list) degree = [0] * n for u, v in p: g[u-1].append(v-1) degree[v-1] += 1 # 拓撲排序的初始節點 q = deque([i for i in range(n) if degree[i] == 0]) # 最長路徑 ans = [0] * n # 做 BFS while q: node = q.popleft() for x in g[node]: degree[x] -= 1 if degree[x] == 0: q.append(x) ans[x] = max(ans[x], ans[node] + times[node]) # 答案就是所有節點的最大值加上自身的時間 return max(ans[i] + times[i] for i in range(n)) while True: try: n = int(input()) a = eval(input()) b = eval(input()) print(sol(n, a, b)) except: break ``` # pC. 逆序數對數量影響最多的數字 逆序題 # pD. 判斷某個單元格能否在特定時間內抵達 ```python= while True: try: x1, y1, x2, y2, t = map(int, input().split(',')) except: break if max(abs(x2-x1), abs(y2-y1)) <= t: print('true') else: print('false') ``` WA # pE. 陣列遊戲 ```python= def sol(arr, k): win = -1 M = max(arr) if k > len(arr): return M for i in range(1, k+1): if arr[0] < arr[i]: break else: return arr[0] for i in range(1, len(arr)): if i+k >= len(arr): return M for j in range(i+1, i+k): if arr[i] < arr[j]: break else: return arr[i] while True: try: n = eval(input()) print(sol(n[0], n[1])) except: break ``` # pF. 兩顆雞蛋 當每次在 `n` 層丟雞蛋,如果他碎了,就會知道是在 `n-1` 層。如果沒碎,那就會往上 `n-1` 層上再丟一次。如此往復可以得到一個公式。 假設有個 `100` 層的建築: $n + (n-1) + (n-2) + (n-3) + (n-4) + … + 1 >= 100$ 而這就是三角形求和的公式,所以我們可以再簡化變成以下: $n (n+1) / 2 >= 100$ ```python= def sol(n): a = 1 while (a*(a+1))/2 < n: a += 1 return a while True: try: n = int(input()) print(sol(n)) except: break ``` # pG. 計算⽅形⼦矩陣數量 `dp`矩陣 ```python= def sol(arr, m, n): if not arr or not arr[0]: return 0 dp = [[0]*(n) for _ in range(m)] ans = 0 for i in range(m): for j in range(n): if arr[i][j] == 1: if i == 0 or j == 0: dp[i][j] = 1 else: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 ans += dp[i][j] return ans while True: try: m, n = map(int, input().split(",")) arr = [] for _ in range(m): arr.append([int(i) for i in input().split(",")]) print(sol(arr, m, n)) except: break ``` # pH. 計算嚴格遞增⼦陣列的數量 ```python= def sol(nums): n = len(nums) if n == 0: return 0 total = 0 l = 1 for i in range(1, n): if nums[i] > nums[i - 1]: l += 1 else: total += (l * (l + 1)) // 2 l = 1 total += (l * (l + 1)) // 2 return total while True: try: n = [int(i) for i in input().split(",")] print(sol(n)) except: break ``` # pI. 所有數字加總 ```python= while True: try: e = input().split(",") M = 0 for i in e: temp = "" for j in i: if j.isdigit(): temp += j if temp: M += int(temp) print(M) except: break ``` # pJ. 簡易加法 ```python= a, b = map(int, input().split()) print(a+b) ``` # pQ. Q1 ```python= print(f"Hello {input()}") ```