Searching for Soulmates

题目描述

农夫约翰的奶牛们都想找到自己的灵魂伴侣——另一头具有相似特征、与自己最大程度兼容的奶牛。每头奶牛的性格用一个整数 $p_i$（$1 \leq p_i \leq 10^{18}$）描述。性格相同的两头奶牛互为灵魂伴侣。 一头奶牛可以通过一次“改变操作”来改变自己的性格：将其乘以 $2$、将其除以 $2$（当 $p_i$ 为偶数时）、或加 $1$。 农夫约翰最初以任意方式将奶牛两两配对。他好奇要让每一对奶牛成为灵魂伴侣，需要多少次改变操作。 对于每一组配对，求该对中第一头奶牛为了与第二头奶牛成为灵魂伴侣，必须进行的最少改变操作次数。

输入格式

第一行包含 $N$（$1\le N\le 10$），表示奶牛配对的数量。 接下来的 $N$ 行每行描述一对奶牛，用两个整数给出她们的性格。第一个数表示必须被改变以匹配第二个数的那头奶牛的性格。

输出格式

请输出 $N$ 行。对于每一对奶牛，输出第一头奶牛将自己的性格变为与第二头奶牛相同所需的最少操作次数。

6
31 13
12 8
25 6
10 24
1 1
997 120

8
3
8
3
0
20

提示

对于第一个测试用例，一种最优的改变序列为 $31 \implies 32 \implies 16 \implies 8 \implies 9 \implies 10 \implies 11 \implies 12 \implies 13$。 对于第二个测试用例，一种最优的改变序列为 $12 \implies 6 \implies 7 \implies 8$。 评分： 测试点 1-4 满足 $p_i \le 10^5$。 测试点 5-12 无额外限制。 题目来源：Quanquan Liu

标签: USACO|2022|Silver

来源

USACO|2022|Silver