---
# System prepended metadata

title: '113_02'

---

# 113_02

# pA. 判斷字串是否有「駝峰」
```python=
s = [int(i) for i in list(input())]
for i in range(1, len(s)-1):
    if max(s[0:i]) < s[i] and max(s[i+1::]) < s[i]:
        print(1)
        break
else:
    print(0)
```

# pB. 判斷「趨勢」
```python=
s = list(input())
if s == sorted(s):
    print(1)
elif s == sorted(s, reverse=True):
    print(2)
else:
    print(3)
```

# pC. 共同的因數
```python=
num = sorted([int(i) for i in input().split(", ")])
for i in range(len(num)-1):
    for j in range(i+1, len(num)):
        if num[j]%num[i]:
            break
    else:
        print(1)
        break
else:
    print(0)
```

# pD. 找出字串中出現最多次的字母
```python=
from collections import Counter
s = list(input())
count = Counter(s)
print(count.most_common(1)[0][0])
```

# pE. 簡化重複字母
```python=
s = input()
temp = 1
ans = ""
for i in range(len(s)-1):
    if s[i] == s[i+1]:
        temp += 1
    else:
        ans += f"{s[i]}{temp}"
        temp = 1
ans += f"{s[-1]}{temp}"
print(ans)
```

# pF. 密碼規則
```python=
time = [0, 0, 0] # 小寫, 大寫, 數字
s = input()
for i in range(len(s)):
    if time[0] == 0 and s[i].isupper():
        print(0)
        break
    if s[i].islower(): time[0] = 1
    if s[i].isupper(): time[1] = 1
    if s[i].isdigit(): time[2] = 1
else:
    if sum(time) == 3:
        print(1)
    else:
        print(0)
```

# pG. 首尾碼相同的子字串個數
```python=
ans = 0
s = input()
for i in range(len(s)):
    for j in range(i+3, len(s)):
        if s[i] == s[j] and s[i].isupper() and s[j].isupper():
            ans += 1
print(ans)
```

# pH. 最長的「特定回文」子字串
[Manacher 演算法](https://www.youtube.com/watch?v=Dg0EP43jTXg)
有效的解決單或雙回文子字串算法
```python=
#Manacher 演算法
s = "$"+"#"+"#".join(list(input()))+"#"+"^"
ans = 0
for i in range(1, len(s)-1):
    temp = 1
    seen = set()
    while s[i-temp] == s[i+temp]:
        if s[i-temp] != "#":
            seen.add(s[i-temp])
        temp += 1
    if len(seen) > 2:
        ans = max(ans, temp-1)
print(ans)
```

# pI. 神秘的「X」
`real` 是實數也就是常數，`imag` 是未知數的係數。
假設題目為 `1+2*X=9`，`eq1` 把題目 `=` 去除加負號，就會變成 `1+2*X-(9)`，接著透過 `eval` 讓未知數放右邊，常數加減放左邊，變成 `{-8+2j}` 此時 `X` 解就變成 `-(-8)/2`。
```python=
eq = input()
eq1 = eq.replace("=","-(") + ")"
c = eval(eq1, {'X': 1j})
print(int(-c.real/c.imag))
```

# pJ. 「三進位」及「六進位」的整數相加
```python=
a, b = input().split(", ")
c = int(a, 3)+int(b, 6)
ans = ""
while c//5:
    c, ans = c//5, ans+str(c%5)
ans += str(c%5)
print(ans[::-1])
```

# pK. 矩陣相乘
```python=
r, c = map(int, input().split())
A = []
for _ in range(r): A.append([int(i) for i in input().split()])
n, m = map(int, input().split())
B = []
for _ in range(n): B. append([int(i) for i in input().split()])
C = [[0]*(m) for _ in range(r)]
for i in range(r):
    for j in range(m):
        temp = 0
        for k in range(n):
                temp += A[i][k]*B[k][j]
        C[i][j] = temp
print("[", end="")
ans = []
for i in C:
    ans.append("["+",".join(map(str, i))+"]")
print(",".join(ans), end="")
print("]")
```

# pL. 3 進位小數轉 9 進位小數
```python=
a, b = input().split(".")
a = int(a, 3)
ans_a = ""
while a:
    a, ans_a = a//9, ans_a+str(a%9)
if ans_a == "":
    ans_a = "0"
ans_b = ""
if len(b)%2: b += "0"
for i in range(0, len(b), 2):
    ans_b += str(int(b[i])*3+int(b[i+1]))
print(ans_a[::-1]+"."+ans_b)
```

# pM. 數獨解題
```python=
sol = []
for _ in range(9):
    temp = input().split(",")
    if "?" in temp:
        x, y = _, temp.index("?")
    sol.append(temp)
flag = False
for i in range(9):
    seen = set()
    for j in range(9):
        if sol[i][j] in seen:
            print(-1)
            flag = True
            break
        seen.add(sol[i][j])
    if flag:
        break
else:
    print(45-sum([int(i) for i in sol[x] if i.isdigit()]))
```

# pN. 重組數字
```python=
from itertools import permutations

n = input()
ans = set()
for i in permutations(n, len(n)):
    temp = ""
    for j in i:
        temp += j
    ans.add(int(temp))
print(len([i for i in ans if i%11 == 0]))
```

# pO. 計算總費用
```python=
up_d = {"E":500, "A":800, "C":200, " ":0}
down_d = {"E":400, "A":800, "C":100, " ":0}
up, down = input().split(",")
p = 0
total = 0
for i in up:
    p += 1
    total += up_d[i]
for i in down:
    p += 1
    total += down_d[i]
if p >= 20:
    print(int(total*0.9))
else:
    print(total)
```

# pP. 轉移文字
```python=
s = ["A", "B", "C", "D", "E", "F"]
a = [int(i) for i in input() if i.isdigit()]
for i in a:
    s.insert(i, s[0])
    s.pop(0)
print("".join(s))
```

# pQ. 最長的共同子字串
```python=
s1 = input()
s2 = input()
ans = 0
for i in range(len(s1)):
    for j in range(i, len(s1)):
        if s1[i:j] in s2:
            ans = max(ans, j-i)
print(ans)
```

# pR. 前後字母交換的字串
```python=
s = list(input())
if len(s)%2:
    for i in range(1, len(s), 2):
        s[i], s[i+1] = s[i+1], s[i]
else:
    for i in range(0, len(s), 2):
        s[i], s[i+1] = s[i+1], s[i]
print("".join(s))
```

# pS. 正好是 10 的倍數
```python=
s = input().upper()
d = [0]*(len(s)+1)
for i in range(1, len(s)+1):
    d[i] = d[i-1]+ord(s[i-1])-64
ans = 0
for i in range(len(d)):
    for j in range(i+1, len(d)):
        if (d[j]-d[i])%10 == 0:
            ans = max(ans, j-i)
print(ans)
```

# pT. 最中間的字元
```python=
s = list(input())
s.sort(key=lambda x: ord(x), reverse=True)
mid = (0+len(s))//2
print(s[mid])
```

# pW. 最長的合法小括號寫法
stack 用法
```python=
q = [-1]
ans = 0
n = list(input())
for i, v in enumerate(n):
    if v == "(":
        q.append(i)
    else:
        q.pop()
        if not q:
            q.append(i)
        else:
            ans = max(ans, i-q[-1])
print(ans)
```

# pX. 出什麼牌最厲害
```python=
key = {"A": 1, "J":11, "Q":12, "K":13}
n = input().replace(" ", "").split(",")
for i in range(len(n)):
    if n[i].isdigit():
        n[i] = int(n[i])
    else:
        n[i] = key[n[i]]
def sol(n):
    temp = set()
    for i in n: temp.add(i)
    temp = list(temp)
    if len(temp) >= 5:
        temp = sorted(temp)
        for i in range(len(temp)-4):
            if temp[i+4] - temp[i] == 4:
                return 1
    from collections import Counter
    count = Counter(n)
    value = list(count.values())
    if 3 in value and 2 in value:
        return 2
    if value.count(2) >= 2 or 4 in value:
        return 3
    if 2 in value:
        return 4
    return 5
print(sol(n))
```

# pY. 巢狀括號最大深度問題 
```python=
n = list(input().replace(" ", ""))
ans = -1
q = 0
for i in n:
    if q:
        if i == "}":
            ans = max(ans, q)
            q -= 1
    if i == "{":
        q += 1
print(ans if q == 0 else -1)
```

# pZ. 數字排列組合
`permutations` 是排序組合不可重複
```python=
from itertools import permutations
n = input()
arr = permutations(n, len(n))
ans = set()
for i in arr:
    ans.add(int("".join(i)))
ans = list(ans)
ans.sort(reverse=True)
for i in ans:
    if str(i) != n:
        print(i)
```

# pAA. 迴圈數字運算
```python=
n = int(input())
ans = [n]
while n != 1:
    if n%2:
        n = n*5+1
    else:
        if n >= 4:
            n //= 4
        else:
            n //= 2
    ans.append(n)
print("->".join(map(str, ans)))
```

# pAB. 數字分群
```python=
def sol():
    n = int(input())
    total = n*(n+1)//2
    if total%2 != 0:
        return 0, n
    target = total//2
    dp = [[]]*(target+1)
    dp[0] = [0]
    for i in range(1, n+1):
        for j in range(target, i-1, -1):
            if dp[j-i]:
                dp[j] = dp[j-i].copy()+[i]
    return dp[target], n
num, n = sol()
if num:
    print(f"YES,[{','.join(map(str, sorted(num)[1::]))}],[{','.join(map(str, sorted([i for i in range(1, n+1) if i not in num])))}]")
else:
    print("NO")
```

# pAC. 蘋果進貨問題
```python=
a, b = map(int, input().split())
print("YES" if (a+b)%3 == 0 else "NO")
```

# pAD. 凱薩密碼
```python=
s = input()
n = int(input())
ans = ""
for i in s:
    if i.isupper():
        print(i, chr((ord(i)-65+n)%26+65))
        ans += chr((ord(i)-65+n)%26+65)
    else:
        print(i, chr((ord(i)-97+n)%26+97))
        ans += chr((ord(i)-97+n)%26+97)
print(ans)
```

# pAE. 總和之半
```python=
def sol():
    num = [int(i) for i in input().split(",")]
    total = sum(num)
    if total%2 != 0:
        return 0
    target = total//2
    dp = [0]*(target+1)
    dp[0] = 1
    for i in range(len(num)):
        for j in range(target, num[i]-1, -1):
            if dp[j-i]:
                dp[j] = 1
    return dp[target]
print(sol())
```