熱門文章

2026年2月14日 星期六

ZeroJudge 解題筆記:c069. 00602 - What Day Is It?

作者:王一哲
日期:2026年2月14日


ZeroJudge 題目連結:c069. 00602 - What Day Is It?

解題想法


將題目需要的功能分拆成以下的自訂函式
  1. is_leap_julian,用來判斷依據儒略曆閏年規則,輸入的年份是否為閏年。
  2. is_leap_gregorian,用來判斷依據格里曆閏年規則,輸入的年份是否為閏年。
  3. is_valid_date,檢查日期是否有效。
  4. get_day_of_week,計算指定日期是星期幾。


Python 程式碼


使用時間約為 9 ms,記憶體約為 3.1 MB,通過測試。
import sys

# 月份名稱對照表
month_names = ("", "January", "February", "March", "April", "May", "June",
               "July", "August", "September", "October", "November", "December")
# 每個月的天數 (非閏年)
month_days = (0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)
# 星期名稱
weekday_names = ("Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday")

def is_leap_julian(year):
    """ 儒略曆閏年規則:能被4整除 """
    return year % 4 == 0

def is_leap_gregorian(year):
    """ 格里曆閏年規則:能被4整除且不被100整除,或者能被400整除 """
    return (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0)

def is_valid_date(month, day, year):
    """ 檢查日期是否有效 """
    # 月份小於 1 或大於 12,日期小於 1,年小於 1
    if month < 1 or month > 12 or day < 1 or year < 1: return False
    # 特殊情況:1752年9月的轉換,沒有9月3日 ~ 13日
    if year == 1752 and month == 9:
        if day == 2 or day == 14: return True
        if 2 < day < 14: return False
    # 該月份的天數
    max_day = month_days[month]
    if month == 2:  # 2月,是否為閏年
        if year < 1752:  # 採用儒略曆
            leap = is_leap_julian(year)
        else:  # 採用格里曆
            leap = is_leap_gregorian(year)
        if leap:  # 如果是閏年,有29天
            max_day = 29
    # 如果 day 小於等於 max_day 為 True,反之為 False
    return day <= max_day

def get_day_of_week(month, day, year):
    """計算指定日期是星期幾"""
    # 題目給定公元1年1月1日是星期六 (Sunday ~ Saturday 的編號分別為 0 ~ 6)
    total_days = 0  # 指定日期為公元1年1月1日之後第幾天
    # 計算從1年到(year-1)年的總天數
    for y in range(1, year):
        if y < 1752:
            leap = is_leap_julian(y)
        else:
            leap = is_leap_gregorian(y)
        total_days += 366 if leap else 365
    # 計算當年1月1日到當月1日的天數
    for m in range(1, month):
        if m == 2:
            if year < 1752:
                leap = is_leap_julian(year)
            else:
                leap = is_leap_gregorian(year)
            total_days += 29 if leap else 28
        else:
            total_days += month_days[m]
    # 加上當月的天數
    total_days += day - 1
    # 特殊調整:1752年9月轉換,橫跨1752年9月14日,要減11天
    if year > 1752 or (year == 1752 and month > 9) or (year == 1752 and month == 9 and day >= 14):
        total_days -= 11
    # 計算星期幾 (1年1月1日是星期六,即weekday=6)
    weekday = (total_days + 6) % 7
    return weekday

""" 主要的解題過程 """
for line in sys.stdin:
    parts = line.strip().split()
    if len(parts) != 3: continue  # 不合法的資料,理論上不會遇到
    month, day, year = map(int, parts)  # 月、日、年轉成整數
    if month == 0 and day == 0 and year == 0: break  # 中止迴圈的條件
    # 檢查日期是否有效
    if not is_valid_date(month, day, year):
        print(f"{month}/{day}/{year} is an invalid date.")
        continue
    # 獲取星期幾
    print(f"{month_names[month]} {day}, {year} is a {weekday_names[get_day_of_week(month, day, year)]}")


2026年2月13日 星期五

ZeroJudge 解題筆記:c061. 00530 - Binomial Showdown

作者:王一哲
日期:2026年2月13日


ZeroJudge 題目連結:c061. 00530 - Binomial Showdown

解題想法


要用計算階乘的對稱性減少計算次數。

Python 程式碼


因為 ZeroJudge 網站大約在2025年10月更新到 Python 3.8.10,可以使用 math.comb 處理這題。使用時間約為 7 ms,記憶體約為 2.8 MB,通過測試。
import sys, math

for line in sys.stdin:
    n, m = map(int, line.split())
    if n == 0 and m == 0: break
    print(math.comb(n, m))

使用時間約為 7 ms,記憶體約為 2.8 MB,通過測試。
import sys

for line in sys.stdin:
    n, m = map(int, line.split())
    if n == 0 and m == 0: break
    ans = 1
    m = min(m, n-m)
    for i in range(1, m+1): ans = ans*(n-m+i)//i
    print(ans)


2026年2月12日 星期四

ZeroJudge 解題筆記:c060. 00392 - Polynomial Showdown

作者:王一哲
日期:2026年2月12日


ZeroJudge 題目連結:c060. 00392 - Polynomial Showdown

解題想法


這題要考慮各種顯示的格式,很麻煩。

Python 程式碼


使用時間約為 19 ms,記憶體約為 3.4 MB,通過測試。
import sys

# 各次方要顯示的變數格式
orders = ("", "x", "x^2", "x^3", "x^4", "x^5", "x^6", "x^7", "x^8")

for line in sys.stdin:
    cofs = list(map(int, line.split()))  # 8 ~ 0 次方的係數
    if all(cof == 0 for cof in cofs):  # 特例,如果所有的係數都是 0
        print("0")  # 印出 0
        continue  # 找下一行
    """ 處理一般的狀況 """
    res = []  # 儲存結果用的串列
    for i, cof in enumerate(cofs):  # 依序讀取係數
        p = 8-i  # 次方
        if cof == 0: continue  # 係數是 0,找下一位
        if cof > 1:  # 係數大於 1
            if res:  # 如果 res 已經有內容,前面要有 " + "
                res.append(f" + {cof:d}{orders[p]:s}")
            else:  # 反之,前面不需要有 " + ",只要有係數、變數、次方
                res.append(f"{cof:d}{orders[p]:s}")
        elif cof == 1:  # 係數等於 1
            if res:  # 如果 res 已經有內容,前面要有 " + "
                if p == 0: res.append(" + 1")  # 常數項,只要有 " + 1"
                else: res.append(f" + {orders[p]:s}")  # 其它項,只要有 " + 變數、次方"
            else:  # 反之,前面不需要有 " + "
                if p == 0: res.append("1")  # 常數項,只要有 "1"
                else: res.append(f"{orders[p]:s}")  # 其它項,只要有變數、次方
        elif cof == -1:  # 係數等於 -1
            if res:  # 如果 res 已經有內容,前面要有 " - "
                if p == 0 res.append(" - 1")  # 常數項,只要有 " - 1"
                else: res.append(f" - {orders[p]:s}")  # 其它項,只要有 " - 變數、次方"
            else:  # 反之,前面不需要有 " - "
                if p == 0: res.append("-1")  # 常數項,只要有 "-1"
                else: res.append(f"-{orders[p]:s}")  # 其它項,只要有 "-變數、次方"
        elif cof < -1:  # 係數小於 -1
            if res:  # 如果 res 已經有內容,前面要有 " - "
                res.append(f" - {-cof:d}{orders[p]:s}")
            else:  # 反之,前面不需要有 " - ",只要有係數、變數、次方
                res.append(f"{cof:d}{orders[p]:s}")
    print("".join(res))  # 將 res 接成字串再輸出


2026年2月11日 星期三

ZeroJudge 解題筆記:c054. 10082 - WERTYU

作者:王一哲
日期:2026年2月11日


ZeroJudge 題目連結:c054. 10082 - WERTYU

解題想法


因為轉換的關係沒有編碼上的規律,用字典建表比較方便。

Python 程式碼


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

table = {'1': '`', '2': '1', '3': '2', '4': '3', '5': '4', '6': '5',
         '7': '6', '8': '7', '9': '8', '0': '9', '-': '0', '=': '-',
         'W': 'Q', 'E': 'W', 'R': 'E', 'T': 'R', 'Y': 'T', 'U': 'Y',
         'I': 'U', 'O': 'I', 'P': 'O', '[': 'P', ']': '[', '\\': ']',
         'S': 'A', 'D': 'S', 'F': 'D', 'G': 'F', 'H': 'G', 'J': 'H',
         'K': 'J', 'L': 'K', ';': 'L', '\'': ';',
         'X': 'Z', 'C': 'X', 'V': 'C', 'B': 'V', 'N': 'B',
         'M': 'N', ',': 'M', '.': ',', '/': '.', ' ': ' '}

for line in sys.stdin:
    s = line.rstrip()
    t = []
    for c in s: t.append(table.get(c, ' '))
    print("".join(t))


2026年2月10日 星期二

ZeroJudge 解題筆記:c050. 00453 - Goldbach's Conjecture

作者:王一哲
日期:2026年2月10日


ZeroJudge 題目連結:c050. 00453 - Goldbach's Conjecture

解題想法


先建立 1000000 以內的質數表 primes,但是不包含 2,因為題目要測試的數字大於 4。如果要測試的數字為 $n$,先用二分搜尋法從表格中找到最接近且大於等於 $n$ 的質數索引值 $idx$,接下來從 3 開始往上找到 $primes[idx]$ 為止,最早找到的解就是差值最大的解。

Python 程式碼


使用時間約為 1 s,記憶體約為 25.5 MB,通過測試。
import sys, bisect

### 建立 1 ~ 1000000 的質數表,不包含 2 ###
maxn = 1000000
sieve = [True]*(maxn+1)
sieve[0] = sieve[1] = False
for i in range(0, maxn+1, 2): sieve[i] = False
for i in range(3, int(maxn**0.5) + 1):
    if sieve[i]:
        for j in range(i*i, maxn+1, i):
            sieve[j] = False
primes = [i for i in range(maxn+1) if sieve[i]]

### 主要的解題過程 ###
result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
    n = int(data[ptr])
    ptr += 1
    if n == 0: break
    idx = bisect.bisect_left(primes, n)
    a, b = 0, 0
    for x in primes[:idx+1]:  # 從 3 開始往上找,最早找到的解就是差值最大的解
        y = n-x
        idy = bisect.bisect_left(primes, y)
        if primes[idy] == y:
            a, b = x, y
            break
    if a == 0 and b == 0:
        reesult.append("Goldbach's conjecture is wrong.\n")
    else:
        result.append(f"{n:d} = {a:d} + {b:d}\n")
sys.stdout.write("".join(result))


2026年2月9日 星期一

ZeroJudge 解題筆記:c049. 00356 - Square Pegs And Round Holes

作者:王一哲
日期:2026年2月9日


ZeroJudge 題目連結:c049. 00356 - Square Pegs And Round Holes

解題想法


先算數學,如果正方形的邊長為 $n$,則圓的半徑為 $r = 0.5 \times (2n - 1)$。接下來用兩層 for 迴圈掃過正方形的右上角每一格,假設正方形正中央為原點 $(0, 0$),格子座標的左下角 $(x, y)$,如果 $(x+1)^2 + (y+1)^2 \leq r^2$ 代表這格在圓之中,如果 $x^2 + y^2 > r^2$ 代表這格在圓之外,再將計算結果乘以 4 就是對應的答案 $inner$ 及 $outer$,圓上的格子數則是 $4n^2 - outer - inner$。

Python 程式碼


使用時間約為 1.2 s,記憶體約為 3.3 MB,通過測試。
import sys

first = True
for line in sys.stdin:
    if not first: print()
    first = False
    n = int(line)
    r = (2*n - 1) * 0.5
    inner, outer = 0, 0
    for x in range(n):
        for y in range(n):
            if (x+1)**2 + (y+1)**2 <= r*r: inner += 1
            elif x**2 + y**2 > r*r: outer += 1
    inner *= 4; outer *= 4
    print(f"In the case n = {n:d}, {4*n*n-outer-inner:d} cells contain segments of the circle.")
    print(f"There are {inner:d} cells completely contained in the circle.")

2026年2月8日 星期日

ZeroJudge 解題筆記:c048. 10161 - Ant on a Chessboard

作者:王一哲
日期:2026年2月8日


ZeroJudge 題目連結:c048. 10161 - Ant on a Chessboard

解題想法


觀察位置的規律,第 1 格在左下角,第 4 格在邊長 $2 \times 2$ 正方形右下角,第 9 格在邊長 $3 \times 3$ 正方形左上角,第 16 格在邊長 $4 \times 4$ 正方形右下角,第 25 格在邊長 $5 \times 5$ 正方形左下角,第 36 格在邊長 $6 \times 6$ 正方形右下角。可以先建表,再用二分搜尋法找 n 在第幾列。也可以直接開根號,向上取整數。

Python 程式碼


使用時間約為 29 ms,記憶體約為 5.2 MB,通過測試。
import sys, bisect

maxn = 44722  # 平方為 2000057284,超出題目上限 2000000000
nums = [i*i for i in range(maxn+1)]  # i 平方的數字,開頭放 0,用二分搜尋法時比較方便
for line in sys.stdin:
    n = int(line)  # 時間 n
    if n == 0: break
    m = bisect.bisect_left(nums, n)  # n 在 nums 之中的棋盤的第 m 列
    b = nums[m] - n  # n 是 nums 第 m 列往回數 b 格
    if m%2 == 1:  # 如果 m 是奇數,先向上,再向左
        if b < m: print(b+1, m)  # 倒過來向右數
        else: print(m, m+m-b-1)  # 倒過來向下數
    else:  # 如果 m 是偶數,先向右,再向下
        if b < m: print(m, b+1)  # 倒過來向上數
        else: print(m+m-b-1, m)  # 倒過來向左數

2026年2月7日 星期六

ZeroJudge 解題筆記:c045. 00490 - Rotating Sentences

作者:王一哲
日期:2026年2月7日


ZeroJudge 題目連結:c045. 00490 - Rotating Sentences

解題想法


這題我在 Python 是用二維串列儲存字串內容,在 C++ 則是用 vector 加 string 儲存內容。先讀取所有的測資,接下來用二層 for 迴圈讀取測資中的字元,外層處理欄位,內容從最後一列讀取到第 0 列。輸出答案時,如果這一列不是整整空白才要輸出。

Python 程式碼


使用時間約為 26 ms,記憶體約為 3.4 MB,通過測試。
import sys

lines = sys.stdin.readlines()  # 一次讀取所有的資測,包含結尾的 \n
n = len(lines)  # 共有 n 列
ans = [[] for _ in range(100)]  # 答案,題目限制每列最多 100 個字元
for c in range(100):  # 欄位,題目限制每列最多 100 個字元
    for r in range(n-1, -1, -1):  # 依序讀取第 n-1 到 0 列
        m = len(lines[r]) - 1
        if c < m: ans[c].append(lines[r][c])  # 如果 r 沒有出界,lines[r][c] 加入 ans[c]
        else: ans[c].append(" ")  # 反之,空格加入 ans[c]
for a in ans:  # 依序讀取 ans 每一列的資料 a
    row = "".join(a)  # 將 a 組成字串 row
    if not row.isspace():  # 如果 row 不是整列空白
        sys.stdout.write(row + "\n")


2026年2月6日 星期五

ZeroJudge 解題筆記:c044. 10008 - What's Cryptanalysis

作者:王一哲
日期:2026年2月6日


ZeroJudge 題目連結:c044. 10008 - What's Cryptanalysis

解題想法


這題可以用表格或字典計數,以下的寫法採用表格計數,用一個長度為 26 的陣列記錄每個字母出現的次數,不是英文字母的字元不需要計數。計數完畢之後,再將次數、字母組成 tuple 或 pair 存入陣列之中,先依照次數由大到小排序,如果次數相同再依照字母由小到大排序。

Python 程式碼


使用時間約為 21 ms,記憶體約為 3.3 MB,通過測試。
n = int(input())
cnt = [0]*26
for _ in range(n):
    s = input()
    for c in s:
        if c.isupper():
            cnt[ord(c) - ord('A')] += 1
        elif c.islower():
            cnt[ord(c) - ord('a')] += 1
ans = [(v, chr(k+ord('A'))) for k, v in enumerate(cnt) if v > 0]
ans.sort(key = lambda x : (-x[0], ord(x[1])))
for a in ans: print(a[1], a[0])


2026年2月5日 星期四

ZeroJudge 解題筆記:c039. 00100 - The 3n + 1 problem

作者:王一哲
日期:2026年2月5日


ZeroJudge 題目連結:c039. 00100 - The 3n + 1 problem

解題想法


用一個自訂函式 cycle 處理數值 n 的循環次數,寫起來會比較方便。函式內部按照題目的要求,分別處理 n 為奇數、偶數兩種狀況,更新 n 的數值。

Python 程式碼


使用時間約為 2.3 s,記憶體約為 3.3 MB,通過測試。
import sys

def cycle(n):
    times = 1  # 如果 n 等於 1,至少有 1 次
    while n != 1:
        times += 1
        if n%2 == 1: n = 3*n + 1
        else: n //= 2
    return times

for line in sys.stdin:
    a, b = map(int, line.split())
    print(f"{a:d} {b:d} ", end="")
    if a > b: a, b = b, a
    imax = 0
    for i in range(a, b+1):
        imax = max(imax, cycle(i))
    print(f"{imax:d}")