В первый день каникул у Буратино была одна золотая монета. Каждый день Буратино выбирал одно из двух: • утром посадить все свои монеты на Поле Чудес, а вечером снять с выросших деревьев урожай: в два раза больше монет, чем было утром; • пойти на весь день в Харчевню Трёх Пескарей, потратив там одну монету. Известно, что сегодня у Буратино n золотых монет. Какое минимальное количество дней могло пройти с начала каникул? Формат входных данных В первой строке записано целое число n — количество мон

Для решения этой задачи можно использовать жадный алгоритм.

Шаги решения:

1. Присвоим переменной “d” значение 0, которая будет отслеживать количество дней, прошедших с начала каникул.
2. Пока количество монет “n” больше 0:
3. Если “n” делится на 2 без остатка, выбираем вариант с полем чудес.
4. Делим “n” на 2 и присваиваем “n” новое значение.
5. Увеличиваем “d” на 1.
6. Если “n” не делится на 2 без остатка, выбираем вариант с харчевней.
7. Вычитаем из “n” 1 и присваиваем “n” новое значение.
8. Увеличиваем “d” на 1.
9. Выводим значение “d” в качестве ответа.

На каждом шаге мы выбираем наилучший вариант, пытаясь уменьшить количество монет “n” как можно быстрее. Выбирая вариант с полем чудес, мы удваиваем количество монет, а выбирая вариант с харчевней, мы тратим одну монету. Поэтому всегда наилучшим решением будет делить количество монет “n” на 2 на каждом шаге, чтобы быстро уменьшить его до 0.

Пример:

Допустим, у Буратино изначально есть 10 монет.

1. “n” = 10, нечетное, выбираем вариант с харчевней.
2. “n” = 9, нечетное, выбираем вариант с харчевней.
3. “n” = 8, четное, выбираем вариант с полем чудес.
4. “n” = 4, четное, выбираем вариант с полем чудес.
5. “n” = 2, четное, выбираем вариант с полем чудес.
6. “n” = 1, нечетное, выбираем вариант с харчевней.
7. “n” = 0, останавливаемся.

Всего прошло 6 дней, поэтому минимальное количество дней, которое могло пройти с начала каникул, равно 6.