Background

3s 1G.

When submitting on Luogu, please use a language version no lower than C++17, and you do not need to include the binary.h header file.

Problem Description

While learning binary operations, Little H encountered a classic problem: given an integer initially equal to $0$, each operation can either multiply it by $2$ or add $1$. Find the minimum number of operations to turn it into a given positive integer $x$. Little H found that the answer can be obtained from the binary representation of $x$.

Based on this problem, Little H proposed the following question: given two positive integers $x, y$, define one operation as one of the following four types:

1. Multiply $x$ by $2$, i.e., $x \leftarrow 2x$;
2. Multiply $y$ by $2$, i.e., $y \leftarrow 2y$;
3. Add $1$ to $x$, i.e., $x \leftarrow x + 1$;
4. Add $1$ to $y$, i.e., $y \leftarrow y + 1$.

Little H wants to know the minimum number of operations needed to make $x$ and $y$ equal. You need to help Little H compute this minimum number of operations.

Implementation Details

Contestants do not need to, and should not, implement the main function.

Contestants need to ensure that the submitted program includes the header file binary.h, i.e., add the following code at the beginning of the program:

#include "binary.h"

Contestants need to implement the following two functions in the submitted source file binary.cpp:

void init(int c, int t);

• $c, t$ represent the test point ID and the number of testdata groups, respectively. $c = 0$ means this test point is the sample.
• For each test point, this function will be called by the grader exactly once at the start of the program.

long long binary(long long x, long long y);

• $x, y$ are the given two numbers.
• This function needs to return the minimum number of operations.
• For each test point, this function will be called by the grader exactly $t$ times.

Note: In all cases, the time required for the grader to run will not exceed $1.8$ seconds. The memory it uses is of fixed size and will not exceed $64$ MiB.

How to Run the Test Program

grader.cpp in the problem directory is a reference implementation of the grader. The grader used in the final evaluation will be different from this reference implementation, so your solution should not rely on the grader implementation.

You can compile an executable program for this problem using the following command:

g++ grader.cpp binary.cpp -o binary -O2 -std=c++14 -static

Input Format

For the compiled executable program:

• The executable will read data from standard input in the following format:
  • The first line contains two non-negative integers $c, t$, representing the test point ID and the number of testdata groups.
  • Then follow $t$ groups of testdata. For each group:
    • The first line contains two positive integers $x, y$, representing the given two numbers.

Output Format

• The executable will output data to standard output in the following format:
  • For each group of testdata, output one line with one integer, representing the minimum number of operations.

0 5
1 2
1 5
3 6
7 33
5 9

1
3
1
4
2

Hint

Files Provided

In the problem directory:

1. grader.cpp is the provided reference implementation of the grader.
2. binary.h is the header file, and contestants do not need to care about its specific contents.
3. template_binary.cpp is the provided sample code, which contestants can refer to and use to implement their own code.

Contestants should back up all provided files. In the final evaluation, only binary.cpp in this problem directory will be tested. Modifications to files other than this program will not affect the evaluation result.

Constraints

For all testdata:

• $1 \le t \le 5 \times 10^7$;
• $1 \le x < y \le 10^{18}$.

::cute-table{tuack}

• Special Property A: $y - x \le 10^3$.
• Special Property B: there exist $k \ge 1$ and $0 \le z < 2^k$ such that $y = x \times 2^k + z$.

Scoring

Note:

• Contestants should not obtain internal information from the grader by illegal means, such as directly interacting with standard input/output streams. Such behavior will be considered cheating.
• The final evaluation grader is implemented differently from the sample grader.

This problem is first subject to the same limits as traditional problems. For example, a compilation error will cause the entire problem to score $0$ points; runtime errors, exceeding the time limit, exceeding the memory limit, etc., will cause the corresponding test points to score $0$ points. Contestants may only access variables they define themselves and variables provided by the grader. Attempting to access other address spaces may lead to compilation errors or runtime errors.

On top of the above conditions:

• For each test point, the program gets full score if and only if the answer returned by the binary function is correct for every call.

Translated by ChatGPT 5