P8093 [USACO22JAN] Searching for Soulmates S

Each of Farmer John’s cows wants to find her soulmate—another cow with similar traits that is as compatible with her as possible. Each cow’s personality is described by an integer $p_i$ ($1 \leq p_i \leq 10^{18}$). Two cows with the same personality are soulmates. A cow can change her personality using “change operations”: multiply it by $2$, divide it by $2$ (when $p_i$ is even), or add $1$. Farmer John initially paired up his cows in an arbitrary way. He is curious how many change operations are needed to make each pair become soulmates. For each pair of cows, find the minimum number of change operations that the first cow in the pair must perform so that she can become soulmates with the second cow.

The first line contains $N$ ($1 \le N \le 10$), the number of cow pairs. The next $N$ lines each describe one pair of cows and contain two integers, their personality values. The first integer is the personality of the cow that needs to be changed to match the other cow.

Output $N$ lines. For each pair, output the minimum number of operations the first cow needs to perform so that her personality matches the second cow’s.

[Sample Explanation] For the first test case, one optimal sequence of operations is $31 \implies 32 \implies 16 \implies 8 \implies 9 \implies 10 \implies 11 \implies 12 \implies 13$. For the second test case, one optimal sequence of operations is $12 \implies 6 \implies 7 \implies 8$. [Constraints] - Test points 1-4 satisfy $p_i \le 10^5$. - Test points 5-12 have no additional constraints. Translated by ChatGPT 5