14016: Пошук споріднених душ - Searching for Soulmates - USACO22JanSilver


Відправити розв'язок

Бали: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem type
Allowed languages
Brain****, C, C++, Java, Pascal, Python, v8js

Кожна з корів Фермера Джона хоче знайти собі споріднену душу. Кожна корова описується цілим числом \(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


Коментарі

Ще немає коментарів.