ZeroJudge 解題筆記：c096. 00700 - Date Bugs

作者：王一哲
日期：2026年3月2日


ZeroJudge 題目連結：c096. 00700 - Date Bugs

解題想法

我只有想到最暴力的作法，用集合 ans 儲存所有第一部電腦所有可能的年份，再依序計算其它電腦可能的年份存入集合 cand，取 ans 與 cand 的交集更新 ans。如果最後 ans 有資料，答案是 ans 之中的最小值；反之則輸出 **Unknown bugs detected.**。這個寫法不快，但是容易操作。

Python 程式碼

暴力解，使用時間約為 23 ms，記憶體約為 6 MB，通過測試。

import sys

ca = 0
maxy = 10000  # 答案上限為 9999
for line in sys.stdin:
    if line.rstrip() == "0": break;
    ca += 1
    if ca > 1: print()  # 如果不是第一筆測資，先印出空行
    n = int(line)  # 電腦數量
    ans = set()  # 第 1 部電腦可能對應的年份
    yi, ai, bi = map(int, sys.stdin.readline().split())  # 顯示年份 yi，於 bi 年出問題，出問題之後回到 ai
    di = bi - ai  # 從 bi 回到 ai 的差值
    for i in range(0, maxy-yi, di): ans.add(yi+i) # 計算可能的年份差
    for _ in range(n-1):  # 讀取 n-1 行資料
        cand = set()  # 第 2 ~ n 部電腦可能對應的年份
        y, a, b = map(int, sys.stdin.readline().split())  # 顯示年份 y，於 b 年出問題，出問題之後回到 a
        d = b - a  # 從 b 回到 a 的差值
        for i in range(0, maxy-y, d): cand.add(y+i)  # 計算可能的年份差
        ans.intersection_update(cand)  # 更新 ans
    print(f"Case #{ca:d}:")
    if ans:  # 如果有交集，印出 ans 之中的最小值
        print(f"The actual year is {min(ans):d}.")
    else:  # 反之，印出 Unknown bugs detected.
        print("Unknown bugs detected.")

C++ 程式碼

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

#include <cstdio>
#include <set>
using namespace std;

int main() {
    int ca = 0, n;  // 第幾次測試，電腦數量
    const int maxy = 10000;  // 答案上限為 9999
    while(scanf("%d", &n) != EOF && n != 0) {
        ca++;
        if (ca > 1) puts("");  // 如果不是第一筆測資，先印出空行
        set<int> ans;  // 第 1 部電腦可能對應的年份
        int y, a, b, d;  // 顯示年份 y，於 b 年出問題，出問題之後回到 a，從 b 回到 a 的差值
        scanf("%d %d %d", &y, &a, &b);
        d = b - a;
        for(int i=0; i<maxy-y; i+=d) ans.insert(y+i); // 計算可能的年份差
        for(int j=0; j<n-1; j++) {  // 讀取 n-1 行資料
            set<int> cand;  // 第 2 ~ n 部電腦可能對應的年份
            scanf("%d %d %d", &y, &a, &b);
            d = b - a;
            for(int i=0; i<maxy-y; i+=d) cand.insert(y+i);  // 計算可能的年份差
            set<int> tmp;  // 暫存要從 ans 之中移除的資料
            for(int a : ans) {  // 更新 ans
                if (cand.find(a) == cand.end()) tmp.insert(a); 
            }
            for(int t : tmp) ans.erase(t);  // 從 ans 之中移除 t
        }
        printf("Case #%d:\n", ca);
        if (!ans.empty()) {  // 如果有交集，印出 ans 之中的最小值
            printf("The actual year is %d.\n", *ans.begin());
        } else {  // 反之，印出 Unknown bugs detected.
            puts("Unknown bugs detected.");
        }
    }
    return 0;
}