CSP-S 2025 第一轮 第27题：程序阅读第 2 题 · 第 6 小题

题目

#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
int cnt_broken = 0;
int cnt_check = 0;
int n, k;
inline bool check(int h) {
    printf("now check:%d\n", h);
    ++cnt_check;
    if (cnt_broken == 2) {
        printf("You have no egg!\n");
        return false;
    }
    if (h >= k) {
        ++cnt_broken;
        return true;
    } else {
        return false;
    }
}
inline bool assert_ans(int h) {
    if (h == k) {
        printf("You are Right using %d checks\n", cnt_check);
        return true;
    } else {
        printf("Wrong answer!\n");
        return false;
    }
}
inline void guess1(int n) {
    for (int i = 1; i <= n; ++i) {
        if (check(i)) {
            assert_ans(i);
            return;
        }
    }
}
inline void guess2(int n) {
    int w = 0;
    for (w = 1; w * (w + 1) / 2 < n; ++w)
        ;
    for (int ti = w, nh = w;; --ti, nh += ti, nh = std::min(nh, n)) {
        if (check(nh)) {
            for (int j = nh - ti + 1; j < nh; ++j) {
                if (check(j)) {
                    assert_ans(j);
                    return;
                }
            }
            assert_ans(nh);
            return;
        }
    }
}
int main() {
    scanf("%d%d", &n, &k);
    int t;
    scanf("%d", &t);
    if (t == 1) {
        guess1(n);
    } else {
        guess2(n);
    }
    return 0;
}

注意：下述的“猜测数”为调用 check 函数的次数（即 $cnt\_check$ 的值）；“猜测正确”的含义为 assert_ans 函数 return true（执行第 25 行所在分支）的情况；所有输入保证 $1 \leq k \leq n$）。

当输入的 $n=100$ 的时候，代码中 $t=1$ 和 $t=2$ 分别需要的猜测次数最多分别为（ ）。

选项

• A. $100, 14$
• B. $100, 13$
• C. $99, 14$
• D. $99, 13$

答案

A

题解

选 A：\(100,14\)。

① 当 \(t=1\) 时

guess1 从 \(1\) 开始逐个调用 check(i)，直到 \(i=k\) 才返回。

因此猜测次数为 \(k\)，当 \(k=100\) 时，最多需要 100 次。

② 当 \(t=2\) 时

先求满足 \[ \frac{w(w+1)}2\ge100 \] 的最小整数 \(w\)。因为 \[ \frac{13\times14}{2}=91<100,\qquad \frac{14\times15}{2}=105\ge100, \] 所以 \(w=14\)。

外层循环先检查第 \(14\) 层，之后每次增加的层数依次为 \(13,12,11,\ldots\)，即检查： \[ 14,\ 27,\ 39,\ 50,\ldots \]

如果第 \(r\) 次外层检查时鸡蛋碎了：

• 外层已经调用 check \(r\) 次；
• 此时 ti 为 \(15-r\)；
• 内层从 nh-ti+1 检查到 nh-1，最多再调用 \(ti-1=14-r\) 次。

所以总次数最多为 \[ r+(14-r)=14. \]

这个上限可以达到：例如 \(k=14\)，先检查 \(14\)，再检查 \(1\) 到 \(13\)，一共 \(1+13=14\) 次，最后 assert_ans(14) 猜测正确。

注意：assert_ans 不计入猜测次数，只有调用 check 才算。