ZeroJudge 解題筆記：a261. 10934 - Dropping water balloons

作者：王一哲
日期：2025年12月27日


ZeroJudge 題目連結：a261. 10934 - Dropping water balloons

解題想法

因為水球最多為 100 顆，丢水球的次數最多為 63 次，先定義一個大小為 $64 \times 101$ 的二維串列，用來表示丢 0 ~ 63 次、共有 0 ~ 100 顆水球，分別可以測試的最高樓層數。假設丢第 $m$ 次、共有 $k$ 顆水球，可以測試的樓層數為以下 3 者相加

1. 第 $m-1$ 次、共 $k-1$ 顆破掉的樓層數
2. 第 $m-1$ 次、共 $k$ 顆沒破的樓層數
3. 這次的測試樓層

因此遞迴關係為 $$ dp[m][k] = dp[m-1][k-1] + dp[m-1][k] + 1 $$ 由於這題的測資很多，為了節省時間，要先建好 $dp$ 表格，再將同一個水球數量 $k$ 分別丢 0 ~ 63 次可以測試的最高樓層數存起來。當讀取到的測資為 $k$、$n$ 時，用二分搜尋法從 $k$ 對應的最高樓層數中找答案。

Python 程式碼

使用時間約為 2 s，記憶體約為 95.2 MB，通過測試。

import sys, bisect

kmax, mmax = 100, 63  # 最多有 100 顆水球、丢 63 次
dp = [[0]*(kmax+1) for _ in range(mmax+1)]  # 丢 0 到 63 次，共有 0 到 100 顆水球，可以測試的最高樓層數
for m in range(1, mmax+1):  # 丢 1 到 63 次
    for k in range(1, kmax+1):  # 1 到 100 顆水球
        # 第 m 次、共 k 顆樓層數 = 第 m-1 次、共 k-1 顆破掉的樓層數 + 第 m-1 次、共 k 顆沒破的樓層數 + 這次的測試
        dp[m][k] = dp[m-1][k-1] + dp[m-1][k] + 1 

kms = dict()  # k 顆水球丢 0 到 63 次可以測試的最高樓層數
for k in range(1, kmax+1):  # 1 到 100 顆水球
    arr = [dp[m][k] for m in range(mmax+1)]  # 取出 k 顆水球丢 0 到 63 次可以測試的最高樓層數組成 list
    kms[k] = arr

lines = sys.stdin.readlines()  # 一次讀取所有測資
result = []  # 要輸出的結果
for line in lines:  # 依序由 lines 讀取單行測資
    k, n = map(int, line.split())  # k 顆水球，最高有 n 層
    if k == 0 or n == 0: continue  # k 或 n 等於 0，讀下一行
    # 如果用 if k == 0 or n == 0: break 會遇到 k == 0 ，下一行回傳 KeyError
    arr = kms[k]  # 取出 k 顆水球丢 0 到 63 次可以測試的樓層數
    idx = bisect.bisect_left(arr, n)  # 用二分搜㝷法找 n 在 arr 之中的索引值 idx
    if idx < len(arr):  # 如果有找到，將字串 idx\n 加到 result
        result.append(f"{idx:d}\n")
    else:  # 反之，將 More than 63 trials needed.\n 加到 result
        result.append("More than 63 trials needed.\n")
sys.stdout.write("".join(result))  # 印出答案

C++ 程式碼

使用時間約為 0.4 s，記憶體約為 376 kB，通過測試。

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

int main() {
    /* 建表 */    
    const int kmax = 100, mmax = 63;  // 最多有 100 顆水球、丢 63 次
    vector<vector<long>> dp ((mmax+1), vector<long> (kmax+1, 0));  // 丢 0 到 63 次，共有 0 到 100 顆水球，可以測試的最高樓層數
    for(int m=1; m<=mmax; m++) {  // 丢 1 到 63 次
        for(int k=1; k<=kmax; k++) {  // 1 到 100 顆水球
            // 第 m 次、共 k 顆樓層數 = 第 m-1 次、共 k-1 顆破掉的樓層數 + 第 m-1 次、共 k 顆沒破的樓層數 + 這次的測試
            dp[m][k] = dp[m-1][k-1] + dp[m-1][k] + 1;
        }
    }
    vector<vector<long>> kms (kmax+1, vector<long> (mmax+1, 0));  // k 顆水球丢 0 到 63 次可以測試的最高樓層數
    for(int k=1; k<=kmax; k++) {  // 1 到 100 顆水球
        for(int m=1; m<=mmax; m++) {  // k 顆水球丢 0 到 63 次可以測試的最高樓層數
            kms[k][m] = dp[m][k];
        }
    }
    /* 讀取測資從表格找答案 */
    long k, n;  // k 顆水球，最高有 n 層
    while(scanf("%ld %ld", &k, &n) != EOF) {
        if (k == 0 || n == 0) continue;  // k 或 n 等於 0，讀下一行
        // 如果用 if (k == 0 || n == 0) break; 會遇到 k == 0 ，下一行回傳 IndexError
        vector<long> arr = kms[k];  // 取出 k 顆水球丢 0 到 63 次可以測試的樓層數
        auto it = lower_bound(arr.begin(), arr.end(), n);  // 用二分搜㝷法找 n 在 arr 之中的迭代器位址
        if (it != arr.end()) {  // 如果有找到，印出索引值
            printf("%ld\n", it - arr.begin());
        } else {  // 反之，印出 More than 63 trials needed.
            puts("More than 63 trials needed.");
        }
    }
    return 0;
}