ZeroJudge 解題筆記：a519. 12459 - Bees' ancestors

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


ZeroJudge 題目連結：a519. 12459 - Bees' ancestors

解題想法

先列出幾代的祖先看一下數量是否有規律，以下各行依序為第幾代，祖先性別 M 為雄性、F 為雌性，祖先數量。

1, F, 1
2, FM, 2
3, FMF, 3
4, FMFFM, 5
5, FMFFMFMF, 8
6, FMFFMFMFFMFFM, 13

第 $n$ 代的祖先數量就是費氏數列 $F(n+1)$ 對應的值。由於這題有多筆測資要查詢對應的數量，可以先建表格，節省查詢的時間。

Python 程式碼

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

import sys

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

for line in sys.stdin:
    n = int(line)
    if n == 0: break
    print(fib[n+1])

C++ 程式碼

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

#include <cstdio>
typedef unsigned long long LL;

int main() {
    LL fib[82] = {0};
    fib[1] = 1;
    for(int i=2; i<=81; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    int n;
    while(scanf("%d", &n) != EOF) {
        if (n == 0) continue;
        printf("%lld\n", fib[n+1]);
    }
    return 0;
}