Олимпиадный тренинг

Задача . Задача Магистра Математикуса


Задача

Темы: Рекурсия

Магистр Математикус обладает волшебными способностями, которые позволяют ему превращать положительные числа в 1 с помощью следующих операций:

  1. Если число четное, он может разделить его на 2.
  2. Если число нечетное, он может увеличить его на 1 или уменьшить на 1.

Сегодня Магистр Математикус задумался над вопросом, какое минимальное количество операций ему необходимо выполнить для превращения числа n в 1 с использованием его волшебных способностей. Помогите ему ответить на этот вопрос.



Входные данные
Программа получает на вход целое число n.

Ограничения на входные данные
  • 1 <= n <= 231 - 1

Выходные данные
Выведите ответ на задачу.
 
 
Примеры
Входные данные Выходные данные
1 8 3
2 7 4


time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python6
Комментарий учителя