Задача №111143. Буфер обмена (ну вот вам другая первая задача)
Барт Симпсон, герой мультсериала «Симпсоны», как наказание за то, что прогуливает уроки, должен послать директору школы электронное письмо. В письме Барт должен N раз набрать фразу «Я больше не буду прогуливать уроки». По мнению директора, написание такого письма произведет на Барта впечатление, и он больше никогда не будет прогуливать школу. Наивный директор!
Вместо того, чтобы N раз набирать требуемую фразу, Барт написал ее один раз, после чего решил воспользоваться буфером обмена. За одну операцию Барт либо копирует все текущее содержимое письма в буфер обмена, либо вставляет скопированный в буфер текст в письмо.
Напишите программу, которая зная, сколько фраз должно быть в письме директору, определит, за какое наименьшее количество операций с буфером обмена Барт сможет составить письмо, количество фраз в котором равно требуемому.
Задано единственное число N, не превосходящее 2·109.
Единственное число — наименьшее число операций с буфером обмена, после которых в письме окажется ровно N фраз.
12
7
Пояснение. После того, как Барт написал первую фразу, он может выполнить такие операции с буфером обмена:
- Копирует текущее содержимое письма (1 фразу).
- Вставляет скопированный текст (фраз в письме становится 2).
- Вставляет скопированный текст (фраз становится 3).
- Вставляет скопированный текст (фраз становится 4).
- Копирует текущее содержимое письма (4 фразы).
- Вставляет скопированный текст (фраз становится 8).
- Вставляет скопированный текст (теперь письмо содержит необходимые 12 фраз).
Подзадача 1. N ≤ 10. Решение оценивается в 20 баллов.
Подзадача 2. N ≤ 3 000. Решение оценивается в 40 баллов.
Подзадача 3. Дополнительные ограничения отсутствуют. Решение оценивается в 40 баллов.
Подзадачи являются вложенными, т.е. баллы за подзадачу ставятся только при прохождении всех меньших подзадач.