# 北商資管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 | 禁止商業用途 | 轉載標記出處 | 改編作品必須在相同條款下分享。
Sign in via Google
Sign in via Facebook
Sign in via X(Twitter)
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Connect another wallet