[语言月赛 202306] std::cerr 的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题是一道 hack 题，要求提交一份数据生成程序，从标准输入读入题号 $x$ ~x~，为对应的问题构造出一组能让题面目标代码输出错误结果或超时的输入数据。核心做法是：问题 $1$ ~1~ 令 $b - c < 0$ ~b - c < 0~，让目标代码所用的整数除法向上取整技巧失效；问题 $2$ ~2~ 输出 $222222$ ~222222~ 个含 std::cerr 的串，把目标代码的缓冲区刷新次数顶到数据规模允许的上限。

分析

核心观察

问题 $1$ ~1~ 的目标代码用 $(a + d - 1)/d$ ~(a + d - 1)/d~（ $d = b - c$ ~d = b - c~）实现 $\lceil a/d \rceil$ ~\lceil a/d \rceil~，该恒等式只在 $d > 0$ ~d > 0~ 时成立，取 $d < 0$ ~d < 0~ 即可让它与真值不符。
问题 $2$ ~2~ 的目标代码对每个含 std::cerr 的串刷新一次标准错误流，刷新次数越多耗时越长；含该子串的串长度至少为 $9$ ~9~，因此刷新次数最多 $222222$ ~222222~ 次，把总长度全部用于这类串即可触到上限。

思路

问题 $1$ ~1~。 记 $d = b - c$ ~d = b - c~。目标代码先算 $d$ ~d~，再输出 $(a + d - 1)/d$ ~(a + d - 1)/d~，其中除法按 C++ 规则向零截断。当 $d > 0$ ~d > 0~ 时，被除数 $a + d - 1 \ge 0$ ~a + d - 1 \ge 0~，非负数的向零截断就是向下取整，于是

$\displaystyle \left\lceil \frac{a}{d} \right\rceil = \left\lfloor \frac{a + d - 1}{d} \right\rfloor = \frac{a + d - 1}{d},\qquad d > 0$

恒等成立，这正是目标代码能算对样例 $(9, 8, 5)$ ~(9, 8, 5)~ 的原因。但当 $d < 0$ ~d < 0~ 时， $a + d - 1$ ~a + d - 1~ 可能为负，向零截断不再等于向下取整，恒等式失效。取最简的一档 $d = -1$ ~d = -1~，即 $b = c - 1$ ~b = c - 1~：

$\displaystyle \left\lceil \frac{a}{d} \right\rceil = -a,\qquad \frac{a + d - 1}{d} = \frac{a - 2}{-1} = 2 - a$

由 $a \ge 1$ ~a \ge 1~ 可知 $2 - a \ne -a$ ~2 - a \ne -a~ 恒成立，故只要满足 $b = c - 1$ ~b = c - 1~，无论 $a$ ~a~ 取多少都能卡掉问题 $1$ ~1~。先前的题解给出的条件「 $b < c$ ~b < c~ 且 $(b - c) \mid a$ ~(b - c) \mid a~」同样可行：此时真值恰为整除的结果，而目标代码把被除数平移了 $d - 1$ ~d - 1~，商与真值至少相差 $1$ ~1~，对这种构造下全部合法数据的穷举验证均成立；本文采用不依赖整除条件的 $d = -1$ ~d = -1~。

问题 $2$ ~2~。 目标代码每读入一个串就做一次子串查找，一旦命中 std::cerr 就向标准错误流输出一次并自增答案。std::cerr 具有 unitbuf 性质，每次插入都立刻刷新缓冲区，对应一次 write 系统调用，累计次数足够多时就会超出题面 $500 \text{ms}$ ~500 \text{ms}~ 的时限。注意每个串至多命中一次，所以刷新次数的上限就是「含 std::cerr 的串」的个数上限；该子串长度为 $9$ ~9~，在串总长度不超过 $2 \times 10^6$ ~2 \times 10^6~ 的前提下

$\displaystyle \left\lfloor \frac{2 \times 10^6}{9} \right\rfloor = 222222$

这就是可达的最大刷新次数，同时 $222222$ ~222222~ 也远小于 $T$ ~T~ 的上界 $10^6$ ~10^6~，数据仍然合法。

具体示例

问题 $1$ ~1~：题面样例 $(a, b, c) = (9, 8, 5)$ ~(a, b, c) = (9, 8, 5)~ 对应 $d = 3 > 0$ ~d = 3 > 0~，真值 $\lceil 9/3 \rceil = 3$ ~\lceil 9/3 \rceil = 3~，目标代码 $(9 + 3 - 1)/3 = 3$ ~(9 + 3 - 1)/3 = 3~，二者相同，卡不掉；而数据 $(a, b, c) = (1, 1, 2)$ ~(a, b, c) = (1, 1, 2)~ 对应 $d = -1$ ~d = -1~，真值 $\lceil 1/(-1) \rceil = -1$ ~\lceil 1/(-1) \rceil = -1~，目标代码 $(1 - 1 - 1)/(-1) = 1$ ~(1 - 1 - 1)/(-1) = 1~，二者不同，hack 成功。

问题 $2$ ~2~：题面样例 $T = 3$ ~T = 3~ 中只有 $2$ ~2~ 个串含 std::cerr，目标代码仅刷新 $2$ ~2~ 次，远不足以超时；而 $T = 222222$ ~T = 222222~、每个串都取 std::cerr 时，单串长度 $9$ ~9~，总长度 $9 \times 222222 = 1999998 \le 2 \times 10^6$ ，目标代码刷新 $222222$ ~222222~ 次，达到上限，hack 成功。

算法步骤

从标准输入读入题号 x。
若 x 等于 $1$ ~1~，输出一行三个整数：a 取 $1$ ~1~、b 取 $1$ ~1~、c 取 $2$ ~2~，此时除数 $d = -1 < 0$ ~d = -1 < 0~。
若 x 等于 $2$ ~2~，令 T 取 $222222$ ~222222~，先输出 T，再输出 T 行字符串 std::cerr。
每行以换行结尾，输出结束（允许文末回车）。

复杂度分析

时间：问题 $1$ ~1~ 为 $O(1)$ ~O(1)~；问题 $2$ ~2~ 为 $O(T)$ ~O(T)~，共输出 $222222$ ~222222~ 行、约 $2.2 \times 10^6$ ~2.2 \times 10^6~ 字节。
空间：问题 $1$ ~1~ 为 $O(1)$ ~O(1)~；问题 $2$ ~2~ 的 C++ 版本逐行写出，附加空间 $O(1)$ ~O(1)~，Python 版本一次性拼出整个输出块，额外占用 $O(T)$ ~O(T)~ 字节（约 $2.2 \times 10^6$ ~2.2 \times 10^6~ 字节）。

实现注意事项

生成器只输出构造出的数据本身，不能输出任何提示或调试信息，也不需要读入题面所述的输入内容。
数据必须严格合法，否则会得到 UKE：问题 $1$ ~1~ 要求 $1 \le a, b, c \le 100$ ~1 \le a, b, c \le 100~、 $b \ne c$ ~b \ne c~ 且无多余内容；问题 $2$ ~2~ 要求 $1 \le T \le 10^6$ ~1 \le T \le 10^6~，每个串非空、字符的 ASCII 值在 $33$ ~33~ 到 $126$ ~126~ 之间、总长度不超过 $2 \times 10^6$ ~2 \times 10^6~，且不能有行末空格（文末回车允许）。
问题 $2$ ~2~ 的突破口是耗时而非输出内容：目标代码把调试信息写进标准错误流，标准输出上的答案始终正确，唯一能翻盘的是刷新缓冲区的开销。
本站的超时判定同时看两项：目标代码实测耗时超过 $500 \text{ms}$ ~500 \text{ms}~，或刷新次数达到数据规模允许的上限 $222222$ ~222222~；本文的数据恰好满足后者。
$222222$ ~222222~ 同时是串数上限与刷新次数上限，这两个上限由同一个事实给出：每个含 std::cerr 的串长度至少 $9$ ~9~，而目标代码对每个串最多刷新一次。
生成器自身的耗时同样计入判题，生成器超时该测试点同样不得分，因此应避免 $222222$ ~222222~ 次零散的系统调用：C++ 版本关闭流同步，Python 版本用乘法拼串后一次性写出。
本地复现时可把生成结果重定向到文件，再喂给题面给出的目标代码，直接观察 $222222$ ~222222~ 次刷新带来的运行时间。

源代码

#include <iostream>
#include <string>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int x;
    std::cin >> x;

    if (x == 1) {
        // 问题 1：取 b = c - 1，即 d = b - c = -1 < 0。
        // 真值 ceil(a / d) = -a，目标代码 (a + d - 1) / d = 2 - a，恒不相同。
        std::cout << "1 1 2\n";
    } else {
        // 问题 2：222222 个 std::cerr，每个 9 字符，总长 1999998 <= 2 * 10^6，
        // 目标代码会刷新 222222 次缓冲区。
        const int T = 222222;
        std::cout << T << '\n';
        const std::string s = "std::cerr\n";
        for (int i = 0; i < T; ++i) std::cout << s;
    }
    return 0;
}

import sys


def main():
    x = int(sys.stdin.readline())

    if x == 1:
        # 问题 1：取 b = c - 1，即 d = b - c = -1 < 0，目标代码必然算错。
        sys.stdout.write("1 1 2\n")
    else:
        # 问题 2：222222 个 std::cerr，每个 9 字符，总长 1999998 <= 2 * 10^6。
        T = 222222
        sys.stdout.write(str(T) + "\n")
        sys.stdout.write("std::cerr\n" * T)


main()

目前没有评论。