---
# System prepended metadata

title: 112-1128

---

# 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()}")
```