P15245 [WC2026] 二进制

3s 1G 在洛谷上提交时，请使用不低于 C++17 的语言版本，并且无需添加 `binary.h` 头文件。

小 H 在学习二进制运算的过程中遇到了一个经典问题：给定一个初始为 $0$ 的整数，每次操作可以将其乘 $2$ 或加 $1$，求将其变为某个给定正整数 $x$ 的最少操作次数。小 H 发现，这可以根据 $x$ 的二进制表示求出答案。 基于这个问题，小 H 提出了以下问题：给定两个正整数 $x, y$，定义一次操作为以下四种之一： 1. 将 $x$ 乘 $2$，即 $x \leftarrow 2x$； 2. 将 $y$ 乘 $2$，即 $y \leftarrow 2y$； 3. 将 $x$ 加 $1$，即 $x \leftarrow x + 1$； 4. 将 $y$ 加 $1$，即 $y \leftarrow y + 1$。 小 H 想知道最少需要多少次操作，才能使得 $x$ 和 $y$ 相等。你需要帮助小 H 求出操作次数的最小值。 ### 【实现细节】 选手不需要，也不应该实现 `main` 函数。 选手需要确保提交的程序包含头文件 `binary.h`，即在程序开头加入以下代码： ```cpp #include "binary.h" ``` 选手需要在提交的程序源文件 `binary.cpp` 中实现以下两个函数： ```cpp void init(int c, int t); ``` - $c, t$ 分别表示测试点编号与测试数据组数。$c = 0$ 表示该测试点为样例。 - 对于每个测试点，该函数会在程序开始运行时被交互库调用恰好一次。 ```cpp long long binary(long long x, long long y); ``` - $x, y$ 表示给定的两个数。 - 该函数需要返回操作次数的最小值。 - 对于每个测试点，该函数会被交互库调用恰好 $t$ 次。 注意：在任何情况下，交互库运行所需时间均不会超过 $1.8$ 秒，所用内存为固定大小，且均不超过 $64$ MiB。 ### 【测试程序方式】 试题目录下的 `grader.cpp` 是交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。 选手可以在本题目下使用如下命令编译得到可执行程序： ```cpp g++ grader.cpp binary.cpp -o binary -O2 -std=c++14 -static ```

对于编译得到的可执行程序： - 可执行文件将从标准输入读入以下格式的数据： - 输入的第一行包含两个非负整数 $c, t$，分别表示测试点编号和测试数据组数。 - 接下来依次为每组测试数据，对于每组测试数据： * 第一行包含两个正整数 $x, y$，表示给定的两个数。

- 可执行文件将输出以下格式的数据至标准输出： - 对于每组测试数据，输出一行一个整数，表示操作次数的最小值。

### 【下发文件说明】 在本试题目录下： 1. `grader.cpp` 是提供的交互库参考实现。 2. `binary.h` 是头文件，选手不用关心具体内容。 3. `template_binary.cpp` 是提供的示例代码，选手可参考并实现自己的代码。 选手注意对所有下发文件做好备份。最终评测时只测试本试题目录下的 `binary.cpp`，对该程序以外文件的修改不会影响评测结果。 ### 【数据范围】 对于所有测试数据，均有： - $1 \le t \le 5 \times 10^7$； - $1 \le x < y \le 10^{18}$。 ::cute-table{tuack} | 测试点编号 | $t =$ | $y \le$ | 特殊性质 | |:-:|:-:|:-:|:-:| | $1 \sim 4$ | $10$ | $10$ | 无 | | $5$ | $10^2$ | $10^2$ | B | | $6$ | ^ | ^ | 无 | | $7,8$ | $10^3$ | $10^3$ | B | | $9 \sim 11$ | ^ | ^ | 无 | | $12$ | $10$ | $10^6$ | A | | $13$ | ^ | ^ | 无 | | $14$ | $10^6$ | ^ | A | | $15$ | ^ | ^ | B | | $16$ | ^ | ^ | 无 | | $17,18$ | ^ | $10^{18}$ | B | | $19 \sim 21$ | ^ | ^ | 无 | | $22 \sim 24$ | $2.5 \times 10^7$ | ^ | ^ | | $25$ | $5 \times 10^7$ | ^ | ^ | - 特殊性质 A：$y - x \le 10^3$。 - 特殊性质 B：存在 $k \ge 1$ 与 $0 \le z < 2^k$ 满足 $y = x \times 2^k + z$。 ### 【评分方式】 注意： - 选手不应当通过非法方式获取交互库的内部信息，如直接与标准输入、输出流进行交互。此类行为将被视为作弊； - 最终的评测交互库与样例交互库的实现不同。 本题首先会受到和传统题相同的限制，例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分。选手只能在程序中访问自己定义的变量以及交互库给出的变量，尝试访问其他地址空间可能导致编译错误或运行错误。 在上述条件基础上： - 对于每个测试点，程序得到满分当且仅当每次调用 `binary` 函数时返回的答案均正确。