Немного отвлечемся от Джокера и вспомним «Темного Рыцаря». Если точнее, сцену с бомбой и детонатором. В альтернативной версии событий Бэтмену не пришлось улетать с бомбой, чтобы она взорвалась далеко от города, потому что был второй способ остановить взрыв.
Сейчас на экране бомбы написаны два натуральных числа $$$a$$$ и $$$b$$$, при этом $$$a \le b$$$. Также, на бомбе есть кнопки, с помощью которых за одно действие можно заменить любое из чисел $$$a$$$ и $$$b$$$ на их среднее геометрическое, округленное вверх, или на их среднее квадратичное, округленное вниз. Напомним, что среднее геометрическое чисел $$$a$$$ и $$$b$$$ равно $$$\sqrt{ab}$$$, а среднее квадратичное равно $$$\sqrt{\frac{a^2+b^2}{2}}$$$.
Бомба будет обезврежена, как только числа на экране станут равны. Помогите Бэтмену обезвредить бомбу за минимальное время, то есть за минимальное количество действий.
В единственной строке даны два натуральных числа $$$a$$$ и $$$b$$$ ($$$1 \le a \le b \le 2000$$$).
Выведите одно число — минимальное количество действий, необходимое для получения двух одинаковых чисел на экране.
2 4
2
12 16
3
В первом тесте Бэтмен может первым действием заменить $$$2$$$ на $$$\ceil[\Big]{\sqrt{2 \cdot 4}} = 3$$$, а вторым действием заменить $$$4$$$ на $$$\floor*{\sqrt{\frac{3^2 + 4^2}{2}}} = 3$$$.
Во втором тесте Бэтмен может первым действием заменить $$$12$$$ на $$$\floor*{\sqrt{\frac{12^2 + 16^2}{2}}} = 14$$$, вторым действием заменить $$$16$$$ на $$$\ceil[\Big]{\sqrt{14 \cdot 16}} = 15$$$, и третьим ходом заменить $$$14$$$ на $$$\ceil[\Big]{\sqrt{14 \cdot 15}} = 15$$$.
Name |
---|