ZeroJudge 解題筆記：a135. 12250 - Language Detection

作者：王一哲
日期：2025年12月22日


ZeroJudge 題目連結：a135. 12250 - Language Detection

解題想法

用字典建對照表，先檢查輸入的字串是否在字典的 key 值之中，如果沒有就輸出 UNKNOWN，如果有就輸出表格中對應的 val。如果是 Python 的 dict，也可以用 dict.get(key, 預設值) 讀取表格中的資料。

Python 程式碼

使用時間約為 17 ms，記憶體約為 2.8 MB，通過測試。

lan = {"HELLO": "ENGLISH",
       "HOLA": "SPANISH",
       "HALLO": "GERMAN",
       "BONJOUR": "FRENCH",
       "CIAO": "ITALIAN",
       "ZDRAVSTVUJTE": "RUSSIAN"}

ca = 0
while True:
    s = input()
    if s == "#": break
    ca += 1
    print(f"Case {ca:d}: ", end="")
    if s not in lan:
        print("UNKNOWN")
    else:
        print(lan[s])

ZeroJudge 解題筆記：a134. 00948 - Fibonaccimal Base

作者：王一哲
日期：2025年12月21日


ZeroJudge 題目連結：a134. 00948 - Fibonaccimal Base

解題想法

由於題目限制要轉換的數字是小於 $100,000,000$ 的正整數，而費氏數列第 40 項就已經是 $102,334,155$，所以建表時只要建前 40 項就可以了。 我另外寫一個轉換數字基底用的函式，假設要轉換的數字是 num，先判斷特例，如果 num 等於 0 直接回傳字串 0，如果 num 等於 1 直接回傳字串 1。接下來用一個 for 迴圈，從表格 fib 後面往前找第一個小於等於 num 的值，以這一項作為起點 start。再用一個 for 迴圈，從 start 往回找到 fib[2] 為止，如果 num 大於等於 fib[j]，要選用這一項，儲存轉換結果的字串 s 加上 1，再將 num 減去 fib[j]；反之，字串 s 加上 0。

Python 程式碼

使用時間約為 19 ms，記憶體約為 2.9 MB，通過測試。

def convert(num):
    if num == 0: return "0"
    if num == 1: return "1"
    start = -1
    for j in range(40, 1, -1):
        if fib[j] <= num:
            start = j
            break
    if start == -1: return "-1"
    s = ""
    for j in range(start, 1, -1):
        if num >= fib[j]:
            s += "1"
            num -= fib[j]
        else:
            s += "0"
    return s

fib = [0]*41
fib[1] = 1
for i in range(2, 41):
    fib[i] = fib[i-1] + fib[i-2]
n = int(input())
for _ in range(n):
    m = int(input())
    print(f"{m:d} = {convert(m)} (fib)")

ZeroJudge 解題筆記：a132. 10931 - Parity

作者：王一哲
日期：2025年12月20日


ZeroJudge 題目連結：a132. 10931 - Parity

解題想法

這題要將一個 10 進位整數轉換成 2 進位字串，再計算字串中 1 的數量。如果用 Python 解題，可以直接用內建的 bin，不過轉換後的字串前面有 0b，要用切片從索引值 2 開始取子字串。如果用 C++ 解題，可以自己寫轉換用的函式，也可以引入 bitset，用 bitset 之中的 to_string() 功能轉換整數。

Python 程式碼

Python 有內建的 10 進位整數轉換成 2 進位字串函式，使用時間約為 8 ms，記憶體約為 2.9 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)
    if n == 0: break
    s = bin(n)[2:]
    p = sum([c == '1' for c in s])
    print(f"The parity of {s:s} is {p:d} (mod 2).")

C++ 程式碼

自己寫將 10 進位整數轉換成 2 進位字串的函式，使用時間約為 1 ms，記憶體約為 316 kB，通過測試。

#include <iostream>
#include <string>
using namespace std;

string bin(int n) {
    string s = "";
    while(n) {
        if (n&1) s = "1" + s;
        else s = "0" + s;
        n >>= 1;
    }
    return s;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    while(cin >> n && n != 0) {
        string s = bin(n);
        int p = 0;
        for(char c : s) {
            if (c == '1') p++;
        }
        cout << "The parity of " << s << " is " << p << " (mod 2).\n";
    }
    return 0;
}

ZeroJudge 解題筆記：a133. 10066 - The Twin Towers

作者：王一哲
日期：2025年12月19日


ZeroJudge 題目連結：a133. 10066 - The Twin Towers

解題想法

這題考最長共同子序列 (longest common subsequence, LCS)，只要找長度，不需要找 LCS 的內容。寫法有兩種，假設兩筆資料 a、b 的長度分別為 n、m，可以用一個 $(n+1) \times (m+1)$ 的二維陣列儲存動態規劃資料，$dp[i][j]$ 代表比較到 $a[i-1]$ 與 $b[i-1]$ 時 LCS 的長度；也可以用兩個陣列儲存資料，用滾動陣列節省記憶體。

Python 程式碼

使用時間約為 1.4 s，記憶體約為 4 MB，通過測試。

import sys

ca = 0
for line in sys.stdin:
    n, m = map(int, line.split())
    if n == 0 and m == 0: break
    ca += 1
    print(f"Twin Towers #{ca:d}")
    a = tuple(map(int, sys.stdin.readline().split()))
    b = tuple(map(int, sys.stdin.readline().split()))
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    print(f"Number of Tiles : {dp[-1][-1]:d}\n")

ZeroJudge 解題筆記：a131. 00739 - Soundex Indexing

作者：王一哲
日期：2025年12月18日


ZeroJudge 題目連結：a131. 00739 - Soundex Indexing

解題想法

可以用陣列建立字母、數字對照表，將字母 A, B, C, ..., Z 對應的數字填入陣列之中。也可以用字典建立對照表，這個寫法比較容易閱讀。

Python 程式碼

使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

table = ('0', '1', '2', '3', '0', '1', '2', '0', '0', '2',
         '2', '4', '5', '5', '0', '1', '2', '6', '2', '3',
         '0', '1', '0', '2', '0', '2')
print("         NAME                     SOUNDEX CODE")
for line in sys.stdin:
    s = line.strip()
    n = len(s)
    last = table[ord(s[0]) - ord('A')]
    result = [s[0]]
    for i in range(1, n):
        if len(result) >= 4: break
        curr = table[ord(s[i]) - ord('A')]
        if curr != '0' and curr != last: result.append(curr)
        last = curr
    while len(result) < 4: result.append('0')
    output = " "*9 + s + " "*(25-n) + "".join(result)
    print(output)
print("                   END OF OUTPUT")

ZeroJudge 解題筆記：a130. 12015 - Google is Feeling Lucky

作者：王一哲
日期：2025年12月17日


ZeroJudge 題目連結：a130. 12015 - Google is Feeling Lucky

解題想法

這題考排序，網站相關度高排前面，如果相關度相同，先讀到的放前面。如果用 Python 解題，可以將網站相關度 val、讀取資料的索引值 idx、網址 url 組成 tuple 再存入串列，排序時用 lambda function 寫比較式 (-x[0], x[1])。如果用 C++ 解題，可以自訂結構體儲存網站相關度 val、讀取資料的索引值 idx、網址 url，資料存入 vector，排序時用 lambda function 寫比較式。

Python 程式碼

使用時間約為 7 ms，記憶體約為 2.9 MB，通過測試。

T = int(input())
for t in range(1, T+1):
    print(f"Case #{t:d}:")
    data = []
    for i in range(10):
        url, v = input().split()
        data.append((int(v), i, url))
    # 排序，相關度高排前面，如果相關度相同，先讀到的放前面
    data.sort(key = lambda x : (-x[0], x[1]))
    vmax = data[0][0]
    for d in data:
        if d[0] < vmax: break
        print(d[2])

ZeroJudge 解題筆記：a111. 12149 - Feynman

作者：王一哲
日期：2025年12月16日


ZeroJudge 題目連結：a111. 12149 - Feynman

解題想法

如果 $n = 1$ 答案為 $1$；如果 $n = 2$，答案為 $1 + 4 = 1 + 2^2 = 5$；如果 $n = 3$，答案有邊長 3 的正方形 1 個，邊長 2 的正方形 4 個，邊長 1 的正方形 9 個，也就是 $1 + 4 + 9 = 1 + 2^2 + 3^2 = 14$。解題時可以建表或是代公式 $$ ans = \sum_{i = 1}^n i^2 = \frac{n(n+1)(2n+1)}{6} $$

Python 程式碼

建表，使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

dp = [0]*101
dp[0] = 0
dp[1] = 1
for i in range(2, 101):
    dp[i] = dp[i-1] + i*i

for line in sys.stdin:
    n = int(line)
    if n == 0: continue
    print(dp[n])

代公式，使用時間約為 20 ms，記憶體約為 3.3 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)
    if n == 0: continue
    print(n*(n+1)*(2*n + 1)//6)

ZeroJudge 解題筆記：a011. 00494 - Kindergarten Counting Game

作者：王一哲
日期：2025年12月15日


ZeroJudge 題目連結：a011. 00494 - Kindergarten Counting Game

解題想法

這題要讀取整行字串之後依序讀取每個字元，用變數 last 記錄目前連續出現的字母數量，如果這個字元是字母則 last 加 1； 反之，前一個單字結束了，如果 last 大於 0，單字數量 cnt 加 1，再將 last 歸零。檢查完整行字串之後，記得要再結算一次，才不會漏掉最後一個單字。

Python 程式碼

使用時間約為 17 ms，記憶體約為 2.8 MB，通過測試。

import sys

for line in sys.stdin:
    last, cnt = 0, 0
    for c in line.strip():
        if c.isalpha(): last += 1
        else:
            if last > 0: cnt += 1
            last = 0
    if last > 0: cnt += 1
    print(cnt)

ZeroJudge 解題筆記：o087. 王子的名字

作者：王一哲
日期：2025年12月14日


ZeroJudge 題目連結：o087. 王子的名字

解題想法

先檢查讀取到的名字是否都是字母，如果有任何一個字元不是字母，分數為 -1；如果所有字元都是字母，按照題目給的規則計分。將分數、索引、名字組成 tuple 或是自訂的 struct ，存入陣列之中，最後按照分數、索引值由小到大排序。

Python 程式碼

使用時間約為 25 ms，記憶體約為 3.3 MB，通過測試。

def Evaluate(Name: str):
    if(type(Name) != str): return -1                              
    Score = 0
    NameLen = len(Name)
    for i in range(NameLen):
        CharCode = ord(Name[i])
        Score += ((CharCode * 1123) % 1002)
        while (CharCode > 0):
            Score += (CharCode % 10)
            CharCode = (CharCode // 10)
    return (Score % 101)

n = int(input())
names = []
for i in range(n):
    name = input()
    score = Evaluate(name)
    names.append((score, i, name))
names.sort()
for score, _, name in names:
    print(f"{name:s} {score:d}")

ZeroJudge 解題筆記：o067. 柯尼斯堡七橋問題

作者：王一哲
日期：2025年12月13日


ZeroJudge 題目連結：o067. 柯尼斯堡七橋問題

解題想法

有奇數條邊的節點數量必須小於等於 2 才有解，可以真的存圖再計算有奇數條邊的節點數量，也可以不存圖、只儲存每個節點是否有奇數條邊。不要真的模擬走訪過程。

Python 程式碼

真的存圖，使用時間約為 0.4 s，記憶體約為 12.7 MB，通過測試。

n, m = map(int, input().split())
graph = dict()
for _ in range(m):
    u, v = map(int, input().split())
    if u not in graph: graph[u] = [v]
    else: graph[u].append(v)
    if v not in graph: graph[v] = [u]
    else: graph[v].append(u)
cnt = 0
flag = True
for v in graph.values():
    if len(v)%2 == 1: cnt += 1
    if cnt > 2:
        flag = False
        break
print("YES" if flag else "NO")

只存每個節點是否有奇數條邊，使用時間約為 0.4 s，記憶體約為 3.4 MB，通過測試。

n, m = map(int, input().split())
vertice = [False]*(n+1)
for _ in range(m):
    u, v = map(int, input().split())
    vertice[u] = not vertice[u]
    vertice[v] = not vertice[v]
cnt = sum(vertice)
print("YES" if cnt <= 2 else "NO")