ZeroJudge 解題筆記：d087. 00107 - The Cat in the Hat

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


ZeroJudge 題目連結：d087. 00107 - The Cat in the Hat

解題想法

寫一個自訂函式 check，輸入起始高度 h、倍率 n，計算總數、高度為 1 的數量、總高度。用 for 迴圈依序測試倍率 1 ~ H-1，用 check 檢查代入的倍率高度為1的貓的數目是否符合測資。

Python 程式碼

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

import sys

def check(h, n):  # 輸入起始高度、倍率
    total, curr, hsum = 1, 1, h  # 總數，目前的數量，總高度
    h //= 1+n  # 新的高度
    while h >= 1:  # 如果 h 大於等於 1 繼續執行
        curr *= n  # 更新數量為 n 倍
        total += curr  # 更新總數
        hsum += curr*h  # 更新總高度
        h //= 1+n  # 更新高度
    return total, curr, hsum  # 回傳總數、高度為 1 的數量、總高度
    
result = []
lines = sys.stdin.readlines()
for line in lines:
    H, M = map(int, line.split())  # 起始高度、高度為 1 的數量
    if H == 0 and M == 0: break  # 如果 H 與 M 皆等於 0，中止迴圈
    total, imin, hsum = H, 1, H  # 試算結果，總數、高度為 1 的數量、總高度
    for i in range(1, H):  # 測試倍率 1 ~ H-1
        total, imin, hsum = check(H, i)  # 回傳測試結果
        if imin == M: break  # 如果 imin 等於 M，找到答案，中止迴圈
    result.append(f"{total-imin:d} {hsum:d}\n")
sys.stdout.write("".join(result))

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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        H, M = map(int, data[ptr:ptr+2])  # 起始高度、高度為 1 的數量
        ptr += 2
        if H == 0 and M == 0: break  # 如果 H 與 M 皆等於 0，中止迴圈
        
        def check(h, n):  # 輸入起始高度、倍率
            isum, curr, hsum = 1, 1, h  # 總數，目前的數量，總高度
            h //= 1+n  # 新的高度
            while h >= 1:  # 如果 h 大於等於 1 繼續執行
                curr *= n  # 更新數量為 n 倍
                isum += curr  # 更新總數
                hsum += curr*h  # 更新總高度
                h //= 1+n  # 更新高度
            return isum, curr, hsum  # 回傳總數、高度為 1 的數量、總高度

        total, imin, hsum = H, 1, H  # 試算結果，總數、高度為 1 的數量、總高度
        for i in range(1, H):  # 測試倍率 1 ~ H-1
            total, imin, hsum = check(H, i)  # 回傳測試結果
            if imin == M: break  # 如果 imin 等於 M，找到答案，中止迴圈
    
        result.append(f"{total-imin:d} {hsum:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

2026年4月3日測試，使用時間約為 0 ms，記憶體約為 1.4 MB，通過測試。2025年7月26日測試，使用時間約為 2 ms，記憶體約為 68 kB，通過測試。兩次測試的程式碼相同，但是使用的記憶體差很多，原因不明。

#include <cstdio>

int main() {
    int H, M;  // 起始高度、高度為 1 的數量
    while(scanf("%d %d", &H, &M) != EOF && (H != 0 || M != 0)) {
        int total=1, curr=1, hsum=H;  // 試算結果，總數、高度為 1 的數量、總高度
        for(int i=1; i<H; i++) {  // 測試倍率 1 ~ H-1
            curr = 1, total = 1, hsum = H;  // 重置
            int h = H/(1+i);  // 新的高度
            while(h >= 1) {  // 如果 h 大於等於 1 繼續執行
                curr *= i;  // 更新數量為 i 倍
                total += curr;  // 更新總數
                hsum += curr*h;  // 更新總高度
                h /= 1+i;  // 更新高度
            }
            if (curr == M) break;  // 如果 curr 等於 M，找到答案，中止迴圈
        }
        printf("%d %d\n", total-curr, hsum);
    }
    return 0;
}