Козак Вус та чарівні черевики#98

Козак Вус та чарівні черевики (Editorial)

Подивімося на закляття з боку двійкового запису швидкості.

Якщо поточна швидкість дорівнює , то після закляття вона стає a + a = 2a або a + (a+1) = 2a + 1. Тобто кожне закляття або дописує до двійкового запису нуль, або дописує одиницю.

Початкова швидкість дорівнює , тобто двійковий запис складається з єдиної одиниці. Після заклять запис міститиме рівно s + 1 двійкових розрядів, а старший розряд завжди залишається одиницею.

Звідси випливає одразу два висновки. По-перше, досяжна будь-яка швидкість k \ge 1: потрібно просто дописувати розряди двійкового запису зліва направо. По-друге, послідовність заклять визначена однозначно, тому й відповідь одна:

s = (\text{кількість двійкових розрядів } k) - 1 = \lfloor \log_2 k \rfloor.

Це ж можна порахувати й циклом у зворотному напрямку: доки k \ne 1, замінюємо на і збільшуємо лічильник.

Оскільки k \le 10^{18}, використовуйте 64-бітний тип; відповідь при цьому не перевищує .