14016: Пошук споріднених душ - Searching for Soulmates - USACO22JanSilver
Кожна з корів Фермера Джона хоче знайти собі споріднену душу. Кожна корова описується цілим числом \(p_i\) (\(1 \leq p_i \leq 10^{18}\)). Дві корови з однаковими \(p_i\) називаються "спорідненими душами". Корова може змінити своє \(p_i\) за допомогою «операції зміни» множенням на \(2\), діленням на \(2\) (якщо \(p_i\) парне), або додаванням \(1\).
ФД спочатку об'єднав корови у пари довільним чином. А тепер хоче дізнатися, скільки операцій він повинен зробити, щоб перетворити кожну пару на "споріднені душі". Для кожної пари визначте мінімальну кількість операцій які потрібно зробити над першою коровою, щоб зробити її "спорідненою душею" з другою коровою.
Формат вхідних даних
Перший рядок містить \(N\) (\(1\le N\le 10\)), кількість пар корів. Кожен з \(N\) рядків описує пару корів як два цілих числа - описують \(p_i\) цих корів. Перше число визначає персональність корови \(p_i\), яка повинна бути змінена, щоб стати рівною другому числу.
Формат вихідних даних
иведіть \(N\) рядків. Для кожної пари виведіть мінімальну кількість операцій які потрібно, щоб перетворити перше число на друге за допомогою описаних операцій.
Приклад вхідних даних
6
31 13
12 8
25 6
10 24
1 1
997 120
Приклад вихідних даних
8
3
8
3
0
20
Для першого прикладу оптимальна послідовність змін: \(31 -> 32 -> 16 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13\).
Для другого прикладу оптимальна послідовність змін: \(12 -> 6 -> 7 -> 8\).
ОЦІНЮВАННЯ:
- У тестах 1-4 \(p_i≤10^5\).
- У тестах 5-12 немає додаткових обмежень.
Автор: Quanquan Liu
Коментарі