ZeroJudge 解題筆記：c031. 00264 - Count on Cantor

作者：王一哲
日期：2026年1月31日


ZeroJudge 題目連結：c031. 00264 - Count on Cantor

解題想法

先觀察數列的特性，第 $i$ 列共有 $i$ 項，數值為 $1/i, 2/(i-1), \dots, (i-1)/2, i/1$，第 $1$ 到 $i$ 列總數 $$ total = 1 + 2 + \dots + i = \frac{i(i+1)}{2} $$ 因此，我先建一個陣列 $nums$ 儲存第 0 列到第 $i$ 列的項目數量，直到數量大於等於 $10^7$ 為止。讀取測資 $n$ 之後，再用二分搜尋法從 $nums$ 之中找 $n$ 的索引值 $m$。若第 $n$ 項為 $p/q$，由於題目的數列順序為 S 形，如果 m 是奇數，代表取數值方向往右上，則 $p = nums[m] - n +1, q = m - p +1$；反之，方向往左下。則 $q = nums[m] - n +1, p = m - p +1$。

Python 程式碼

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

import sys, bisect

nums = [0]
i, tot = 0, 0
while tot < 1E7:
    i += 1
    tot += i
    nums.append(tot)

for line in sys.stdin:
    n = int(line)
    m = bisect.bisect_left(nums, n)
    if m%2 == 1:
        p = nums[m] - n + 1
        q = m - p + 1
    else:
        q = nums[m] - n + 1
        p = m - q + 1
    print(f"TERM {n:d} IS {p:d}/{q:d}")

C++ 程式碼

使用時間約為 2 ms，記憶體約為 312 kB，通過測試。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {0};
    int i = 0, tot = 0;
    while(tot < 10000000) {
        i++;
        tot += i;
        nums.push_back(tot);
    }
    int n, p, q;
    while(scanf("%d", &n) != EOF) {
        int m = lower_bound(nums.begin(), nums.end(), n) - nums.begin();
        if (m%2 == 1) {
            p = nums[m] - n + 1;
            q = m - p + 1;
        } else {
            q = nums[m] - n + 1;
            p = m - q + 1;
        }
        printf("TERM %d IS %d/%d\n", n, p, q);
    }
    return 0;
}