---
# System prepended metadata

title: 北商資管114年程式競賽初階組詳解

---

# 北商資管114年程式競賽初階組詳解
> 十校聯盟程式競賽 - 初階組 詳解
---

# 1. 出現最多次的字母
用字典去紀錄每個字母出現的次數。
> 要注意的是123這種輸入。

```python=
s = input()
d = {}

for i in range(len(s)):
    if s[i].isalpha():
        d[s[i]] = d.get(s[i],0)+1

if not d:
    print(0)
else:
    mx = max(d.values())
    count = sum(1 for k in d if d[k] == mx)
    print(1 if count >= 2 else 0)
```

# 2. 判斷字串的趨勢
透過建表mapping的方式快速查詢。
```python=
s = input().strip()

d = {}
for i, c in enumerate('0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'):
    d[c] = i
li = [d[c] for c in s]

if all(li[i] > li[i-1] for i in range(1, len(li))):
    print(1)  
elif all(li[i] < li[i-1] for i in range(1, len(li))):
    print(2) 
else:
    print(3)

```
# 3. 相同內容的子字串
透過線性搜索及分段儲存來記錄。
```python=
n = input()
li = ['0']
for i in n:
    if i!=li[-1][-1]:li.append(i)
    else: li[-1] += i
mx = max(len(i) for i in li)
print(mx)
```
# 4. 反向放置長單字
透過tmp來將單詞放入li中，達成 **"只要不是英文字母都split掉"** 的想法。
```python=
s = input()
li = []
tmp = ''
for i in s:
    if i.isalpha():tmp+=i
    else:
        li.append(tmp)
        tmp = ''
li2 = [i for i in li if len(i) >=4]
print(' '.join(reversed(li2)))
```
# 5. Excel 的儲存格個數
水題。
```python=
a,b = input().split(", ")
wei = abs(ord(a[0].upper()) - ord(b[0].upper()))+1
hei = abs(int(a[1:])-int(b[1:]))+1
print(wei*hei)
```
# 6. 3 迴文的個數
雙迴圈使i,j固定距離4(含)以上。
> 移動窗戶(sliding window)實作。
```python=
s = input()
ans = set()
for i in range(0,len(s)):
    for j in range(i+4,len(s)+1):
        if s[i:j]==s[i:j][::-1] and len(set(i for i in s[i:j]))>=3:
            ans.add(s[i:j])
print(len(ans))
```
# 7. 安全渡河的乘船法
先將所有排列列出後，在刪去不符合規則的。
```python=
from itertools import permutations

s = input().strip()
d = {''.join(p) for p in permutations(s)}
li = [p for p in d if 'cd' not in p and 'cr' not in p]

print(len(li))

```
# 8. 神秘的X與Y
用replace()替換掉X，Y就好。
用枚舉的方式，一一將所有可能性帶入。
> 執行時間有2秒，絕對夠。
```python=
n,ans = input().split("=")
li = []
for x in range(1,101):
    for y in range(1,101):
        tmp = n.replace('X',str(x))
        t = eval(tmp.replace('Y',str(y)))
        if str(int(t)) == ans:
            li.append((x,y))
print(len(li))
```
# 9. 二進位的 bit 1 個數
水題
```python=
li = list(map(int,input().split(", ")))
a = max(li)-min(li)

def tB(n):
    ans = ''
    while n!=0:
        ans +=str(n%2)
        n//=2
    return ans

ans = sum(1 for i in tB(a) if i=='1')
print(ans)
```
# 10. 沒有重覆字元的字串個數
用bool指標"ok"來記錄是否有找到相同字，如果有相同字，ok就變成false。
```python=
li = list(input().split(", "))
cnt = 0
for w in li:
    ok = True
    for i in range(1, len(w)):
        if w[i] == w[i - 1]:
            ok = False
            break
    if ok:
        cnt += 1
print(cnt)
```
# 11. Pascal’s Triangle 第 n 列
高一數學。
> 巴斯卡三角形的第 i 行第 j 個數字 = C(i, j)

math套件的comb可以幫我們快速計算C(i取j)
```python=
from math import comb

n = int(input())
li = []
for i in range(n):
    li.append(list(str(comb(i, j)) for j in range(i + 1)))
print(' '.join(li[-1]))
```
# 12. 羅⾺數字解析器
只要左邊的數比當前的數小，就減左邊的數。
```python=
s = input().strip().upper()
d = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
ans = 0
for i in range(len(s)-1):
    if d[s[i]] < d[s[i+1]]:
        ans -= d[s[i]]
    else:
        ans += d[s[i]]
ans += d[s[-1]]
print(ans)
```
# 13. 數字重排差值
陷阱題，你可能會以為用`import ppermutations`來做排列，再者最大最小值，但這樣 **一定會超時**。
> 題目說找最大跟最小，其實就是升幂跟降冪兩個排列。

```python=
n = input().strip()
s = sorted(n)
mn = int(''.join(s))
mx = int(''.join(s[::-1]))
print(mx - mn)
```
# 14. 進位換算
一樣使用mapping的方式快速完成。
```python=
S,M,N = input().split()
M = int(M)  
N = int(N) 

def T(N,R):
    ans = ''
    mapping = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    while N>0:
        ans += mapping[N%R]
        N//=R
    return ans[::-1]

k = T(int(S, M), N)
print(k)
```
# 15. 尋找最接近質數 
def p()函式來檢查該數是否是質數。
> 因為題目說距離一樣的話先輸出小的，所以右邊(<)先檢查。

注意1**不是**質數。
:::success
檢查到n是不是質數只需要檢查到$\sqrt{n}$
:::
```python=    
def p(x):
    if x < 2:
        return False
    if x == 2:
        return True
    if x % 2 == 0:
        return False
    for i in range(3, int(x**0.5) + 1, 2):
        if x % i == 0:
            return False
    return True

n = int(input())
d = 1
while True:
    if p(n - d):
        print(n - d)
        break
    if p(n + d):
        print(n + d)
        break
    d += 1
```
# 16. 系統異常⾏為偵測
全部讀取完，在開始進行判斷。
採用dict+list的資料結構儲存資料
```python=
n=int(input())
d={}
for _ in range(n):
    a,t,i=input().split()
    h,m=map(int,t.split(':'))
    t=h*60+m
    if a not in d:d[a]=[]
    d[a].append((t,i))
r=[]
for a,l in d.items():
    for j in range(len(l)):
        for k in range(j+1,len(l)):
            if abs(l[j][0]-l[k][0])<=10 and l[j][1]!=l[k][1]:
                r.append(a)
                break
        else:continue
        break
print('\n'.join(sorted(r))if r else'None')
```
# 17. 簡易凱薩加密
轉成ASCII碼再加上來就好。
```python=
shift = int(input())
s = input()

res = ''
for ch in s:
    if 'A' <= ch <= 'Z':
        res += chr((ord(ch) - 65 + shift) % 26 + 65)
    elif 'a' <= ch <= 'z':
        res += chr((ord(ch) - 97 + shift) % 26 + 97)
    else:
        res += ch
print(res)
```
# 19. 組成相同長度的字串
```python=
li = list(len(i) for i in map(str,input().split(', ')))
li.sort()

r = len(li)//2
T = False
for i in range(len(li)-r):
    s = sum(li[i:i+r])
    if sum(li)-s == s:
        T = True
print('1'if T else '0')
``` 
# 20. 求中位數
水到靠杯的題目。
```python=
li1 = list(map(int,input().split(', ')))
li2 = list(map(int,input().split(', ')))
li = sorted(li1+li2)
print(li[len(li)//2])
```
# 21. 反轉數字
分別將小數點左右的數字取出後做反轉即可。
```python=
s = input()
t, left, right = s[0], s[1:s.index('.')], s[s.index('.')+1:]

ans = ''.join(i for i in left if i.isnumeric() and i != '0')[::-1]
ans2 = ''.join(i for i in right if i.isnumeric() and i != '0')[::-1]

print(f'{t if t!="+" else ""}{ans}.{ans2}')
```
:::danger
小心`print(f'{t if t!='+' else ''}{ans}.{ans2}')`全用單引號的話會讓DOMjudge 出現編譯錯誤。
:::

# 22. 找出共同最長的字尾
取出一個做為target，其他人只要都=target就OK，若有一個不=target，就直接終止迴圈。
> 寫法一，快速

```python=
li = input().split(', ')
s = min(len(i) for i in li)

ans = ''
for i in range(1, s + 1):
    tar = li[0][-i]
    if all(j[-i] == tar for j in li):
        ans = tar + ans
    else:
        break

print(ans if ans else "*")
```
> 寫法二，直觀邏輯
```python=
li = input().split(', ')
s = min(len(i) for i in li )

ans = ''
c = -1
T = None

for _ in range(s):
    tar = li[0][c]
    for i in range(1,len(li)):
        
        if li[i][c] == tar:
            T = True
        else:
            T = False
            break
            
    if T:ans= tar + ans
    else: break
    c-=1
print(ans if ans else "*")
```
# 23. 洗了n次的撲克牌
因為只要洗過的牌都會被放到後面，所以我們可以去比較，"元順序"中，哪些牌還保留著原有的順序沒動。
```
ori = ['A','2','3','4','5','6','7','8','9','10','J','Q','K']
li = input().split(',')
```
也就是說我只需要從ori中，取出一個從i開始的子陣列，如果這個子陣列中的每個元素，都已相對位置的方式出現在li中，則i就是被洗牌的次數。
:::success
簡單來說，就是找ori[i:] 這個子陣列是否按照順序(無按照絕對位置)出現在li中。
(就是比較ori[i:]是否是li的子陣列)
:::
```python=
def sq(o, l):
    it = iter(l)
    return all(any(x == y for y in it) for x in o)

ori = ['A','2','3','4','5','6','7','8','9','10','J','Q','K']
li = input().split(',')
for i in range(13):
    if sq(ori[i:], li):
        print(i)
        break
```
:::spoiler 舉例說明
如果我今天從ori的2(value = 3)開始往後與li比較，如果3~K都在li裡面且按照遞增順序(也就是3~K)，那就代表只有A,2這兩張牌有被洗牌，則ori的index2(剛剛取出3的位置)就是洗牌的張數!!
:::
:::info
**什麼是iter()??**

單向消耗的指標，
每次找成功一次，iterator 就會停在那個位置的「後面」。
所以下一個 x 會接著繼續往後找。
:::
:::spoiler 過程演示
| 步驟   | x (o中當前) | 內層 it 位置 | 比對過程                                   | 結果           | it 停在哪              |
| ---- | -------- | -------- | -------------------------------------- | ------------ | ------------------- |
| 1️⃣  | '8'      | 開頭 (`4`) | 4≠8, 3≠8, 5≠8, 6≠8, 2≠8, 7≠8, **8=8✅** | `any()`→True | 停在 '8' 之後（目前指向 '9'） |
| 2️⃣  | '9'      | 從 '9' 開始 | **9=9✅**                               | True         | 停在 '9' 之後（指向 'A'）   |
| 3️⃣  | '10'     | 從 'A' 開始 | A≠10, **10=10✅**                       | True         | 停在 '10' 之後（指向 'J'）  |
| 4️⃣  | 'J'      | 從 'J' 開始 | **J=J✅**                               | True         | 停在 'J' 之後（指向 'Q'）   |
| ✅ 結果 | —        | —        | 所有 x 都成功                               | `all()`→True | —                   |

:::

# 24. 縱列相同的文字
用消耗指標iter()來快速將題目的輸入分成3組。
```python=
s = input()
k = len(s)//3
n = iter(s)
li = [[next(n) for _ in range(k)] for _ in range(3)]

ans = []
for i in range(k):
    if li[0][i] == li[1][i] == li[2][i]:
        ans.append(int(li[0][i]))
ans.sort()

print(''.join(str(i) for i in set(ans)) if ans else 'N')
```
# 25. 重組成最大數字
題目有點小陷阱，不是只按照", "來做分割就好，為了避免有些測資有空白，有些沒有，建議疑慮:
```python
n = input().replace(' ', '').split(',')
```
```python=
from functools import cmp_to_key

def f(x, y):
    
    if x + y > y + x:# 這裡是指字串的相加
        return -1
    elif x + y < y + x:
        return 1
    else:
        return 0

n = input().replace(' ', '').split(',')
n.sort(key=cmp_to_key(f))

print(''.join(n))
```
:::info
**`from functools import cmp_to_key`**
是一個可以讓你自訂排序規則的function。
:::
:::spoiler 比較規則
-1 → 代表 **左**邊在**右**邊**前面**
1 → 代表 **左**邊在**右**邊**後面**
0 → 代表 兩者相等（順序不變）
:::
# 26. 最長的連續序列
```python=
li = sorted(map(int, input().split(',')))

tmp = ans = 1
for i in range(1, len(li)):
    if li[i] - li[i - 1] == 1:
        tmp += 1
    else:
        ans = max(ans, tmp)
        tmp = 1

print(max(ans, tmp))
```

# 27. 最少的轉動次數
限制一個數在指定範圍n中，就是直接%n
```python=
a,b = input().split(", ")

ans = 0
for a,b in zip(a,b):
    a,b = int(a),int(b)
    ans += min((b - a) % 10, (a - b) % 10)

print(ans)
```
:::info
zip() 會把多個可迭代物件"一個一個對位打包成 tuple"的形式組合起來。
:::spoiler 範例
```python=
a = [1, 2, 3]
b = [4, 5, 6]

print(list(zip(a, b)))
```
:::
# 28. 最長的子序列
跟23題很像，都是要尋找子序列，但23題有給你ori[i:]讓你去找，現在沒了

> 演算寫法

```python=
import bisect

li = list(map(int, input().replace(" ", "").split(",")))

tails = []
for num in li:
    pos = bisect.bisect_left(tails, num)
    if pos == len(tails):
        tails.append(num)
    else:
        tails[pos] = num
print(len(tails))
```
:::success
bisect.bisect_left(li, num) 具體做的事是：
在一個「已排序」的列表 li 中，找到「第一個大於等於 num」的索引位置。
:::

:::spoiler 演算過程
假設輸入：
```
li = [10, 9, 2, 5, 3, 7, 101, 18]
```
我們維護一個空陣列：
```
tails = []
```
| 處理值 | tails          | bisect_left 結果 | 更新說明                |
| --- | -------------- | -------------- | ------------------- |
| 10  | [10]           | -              | 新增第一個數              |
| 9   | [9]            | idx=0          | 取代 tails[0]=9（更小尾巴） |
| 2   | [2]            | idx=0          | 取代 tails[0]=2       |
| 5   | [2, 5]         | idx=1          | 新增在尾端（長度 +1）        |
| 3   | [2, 3]         | idx=1          | 取代 tails[1]=3       |
| 7   | [2, 3, 7]      | idx=2          | 新增尾端（長度 +1）         |
| 101 | [2, 3, 7, 101] | idx=3          | 新增尾端                |
| 18  | [2, 3, 7, 18]  | idx=3          | 取代 tails[3]=18      |


最後 tails = [2, 3, 7, 18]
LIS 長度 = len(tails) = 4
:::

> 直觀寫法 時間複雜度 ≈ O(n²)。
```python=
li = list(map(int,input().replace(" ", "").split(",")))
sli = sorted(li)

ans = []
for i in sli:
    idx = li.index(i)
    tmp = [0]
    
    for j in range(idx,len(li)):
        if li[j]>tmp[-1]:tmp.append(li[j])

    ans.append(len(tmp)-1)
print(max(ans))
```

# 29. 奇幻數
用雙重迴圈去跑就夠快了。
```python=
n = input()
for i in range(len(n)):
    for j in range(i+1,len(n)):
        cop = list(n)
        cop[i],cop[j] = n[j],n[i]
        val = int(''.join(cop))
        if val % 29 == 0:
            print(1)
            break
    else:
        continue
    break
else:
    print(0)
```
---

:::info
趁機宣傳一下我自己的個人網站跟Youtube頻道 !!

**[個人網站](https://hyc.eshachem.com/) | [Youtube頻道](https://www.youtube.com/@Hy.C)**
:::
@2025 Hy.C 陳毓
> Copyright ©Hy.C 陳毓 CC BY-NC-SA 4.0 | 禁止商業用途 | 轉載標記出處 | 改編作品必須在相同條款下分享。