你好！我是金牌教练。为了方便你快速搭建 OJ（在线判题系统）测试环境，我为你编写了一个集成化的数据生成器与标程（Generator & Solver）。

这个程序将按照 NOI 竞赛的标准，生成 10 组测试点。设计思路是：前两组数据极小，暴力可过；中间增加边界条件；后三组数据达到极限规模 $2^{31}-1$，必须使用防溢出的 $O(\log n)$ 二分算法才能满分。

一、 测试点设计说明

二、 数据生成器 C++ 代码

该程序采用 C++14 标准。它会自动运行标程逻辑并产生对应的 .in 和 .out 文件。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <random>
#include <algorithm>
#include <ctime>

using namespace std;

// 使用 long long 防止在计算中点时发生溢出
typedef long long ll;

/**
 * 标程：最优解 (二分查找第一个错误版本)
 * 时间复杂度: O(log n)
 * 空间复杂度: O(1)
 */
ll solve(ll n, ll k) {
    ll left = 1, right = n;
    ll ans = n;
    while (left <= right) {
        // 防溢出写法：mid = left + (right - left) / 2
        ll mid = left + (right - left) / 2;
        // 模拟 isBadVersion 接口：如果 mid >= k，说明当前是坏版本
        if (mid >= k) {
            ans = mid;      // 记录当前坏版本，继续向左尝试找更早的
            right = mid - 1;
        } else {
            left = mid + 1; // 当前是好版本，坏版本一定在右侧
        }
    }
    return ans;
}

/**
 * 数据构造器逻辑
 */
void generate_test_case(int id, ll n, ll k) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";
    
    // 生成输入文件
    ofstream fout(in_name);
    if (fout.is_open()) {
        fout << n << " " << k << endl;
        fout.close();
    }

    // 生成输出文件 (运行标程)
    ofstream fans(out_name);
    if (fans.is_open()) {
        fans << solve(n, k) << endl;
        fans.close();
    }
    
    cout << "Test Case " << id << ": n = " << n << ", k = " << k << " [Done]" << endl;
}

int main() {
    // 随机数引擎
    mt19937_64 rng(time(0));
    
    // 测试点 1-2: 小规模数据
    generate_test_case(1, 10, 7);
    generate_test_case(2, 100, 42);
    
    // 测试点 3: 最小规模边界
    generate_test_case(3, 1, 1);
    
    // 测试点 4-5: 极小规模边界
    generate_test_case(4, 2, 1);
    generate_test_case(5, 2, 2);
    
    // 测试点 6-7: 中等规模 (区分 O(n) 与 O(log n))
    // 10^8 级别，暴力扫描需 0.5s~1.0s，二分仅需 <1ms
    generate_test_case(6, 100000000, 99999999);
    generate_test_case(7, 200000000, 150000000);
    
    // 测试点 8-10: 极大规模 (2^31 - 1)
    // 必须使用 long long 运算，否则 (left + right) 会溢出成负数
    ll INT_MAX_VAL = 2147483647LL;
    
    generate_test_case(8, INT_MAX_VAL, 1);          // 开头错误
    generate_test_case(9, INT_MAX_VAL, INT_MAX_VAL); // 结尾错误
    
    // 随机极大值
    uniform_int_distribution<ll> dist(1, INT_MAX_VAL);
    generate_test_case(10, INT_MAX_VAL, dist(rng));
    
    cout << "\nAll 10 test cases generated successfully." << endl;
    return 0;
}

三、 技术说明与优化细节

1. 文件大小控制：

   • 本题每个输入文件只包含两个整数（$n$ 和 $k$），文件大小仅为几十个字节。
   • 10 组文件的总大小远小于 1MB，符合 OJ 上传的最优要求。

2. 防溢出处理（重要）：

   • 题目给定的 $n$ 最大为 $2^{31}-1$，即 INT_MAX。
   • 在计算中点时，如果使用 (left + right) / 2，当 left 和 right 均较大时，它们的和会达到 $4.2 \cdot 10^9$，超出了 32 位有符号整数 int 的范围，导致结果为负数。
   • 生成器和标程统一使用 long long 类型进行计算，这是 NOI 竞赛中保证健壮性的首选方案。

3. 区分算法复杂度：

   • 暴力解法：在测试点 1-5 表现良好，但在测试点 6-7 会感到吃力，在测试点 8-10 面对 $21$ 亿次询问时，必然会导致 TLE。
   • 二分答案：在所有测试点均可在 $O(\log n)$（约 31 次计算）内完成，表现极其稳定。

4. 非递归实现：

   • solve 函数采用迭代（while 循环）写法，避免了在递归深度过大时可能产生的系统栈溢出风险。

四、 如何使用

1. 将上述代码保存为 gen.cpp。
2. 使用 g++ gen.cpp -o gen -std=c++14 编译。
3. 运行 ./gen，它会在当前目录下生成 1.in, 1.out ... 10.out。
4. 将这些文件打包上传到你的 OJ 即可。