Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






J. Чудовищная экономия

Задачу добавил: alef

Успешно сдано решений: 29

ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
input.txt
вывод
output.txt

На досуге Программист играет в одну игру, которую сам же и написал.

В этой игре есть два монстра:

Большой Линейный Монстр. Каждый его удар уменьшает здоровье героя на 100500. Чтобы убить его, герою требуется нанести ему 11 ударов;

Большой Логарифмический Монстр. Каждый его удар делит здоровье героя на 2 с округлением вниз до ближайшего целого. Чтобы убить его, герою также необходимо нанести ему 11 ударов.

Один раз в час здоровье героя полностью восстанавливается, и он отправляется сражаться с монстрами. Бой происходит так: сначала игрок выбирает любого из монстров и ударяет его. После этого монстры наносят игроку удары в следующем порядке: сначала Большой Логарифмический Монстр (если он еще жив), а потом Большой Линейный Монстр (если он еще жив). Бой повторяется, пока не будет повержен герой или оба монстра. Как и всегда, герой или монстр считается поверженным, если его здоровье перестает быть положительным.

Однажды монстрам надоело, что их постоянно убивают. Некарат, старый знакомый Большого Логарифмического Монстра, оказался слишком занят умножением игроков на ноль в четвертом акте. Монстры посовещались между собой и решили купить в магазине артефактов адскую линейку сокрушения, которая увеличивает повреждения, наносимые Большим Линейным Монстром. Они хотят, чтобы они оба гарантированно выжили в сражении с героем, здоровье которого равно H. В магазине продаются разные линейки, при этом чем большую прибавку урона дает линейка, тем дороже она стоит. Монстры очень экономны, и хотят приобрести наименее дорогую линейку, которая позволит им решить их проблему.

Ваша задача — определить минимальное значение для прибавки урона, который должна обеспечить такая линейка.

Входные данные

В первой строке содержится единственное целое число H (205624024 ≤ H ≤ 1018) — здоровье героя, который отправляется сражаться с монстрами.

Выходные данные

В первой строке выведите единственное целое число — минимально возможное значение для прибавки урона, которое позволит монстрам выжить в сражении.

Примеры тестов

Входные данные
205624024
Выходные данные
1
Входные данные
1000000000000000000
Выходные данные
488758553174182

Сдать задачу

Задать вопрос жюри по этой задаче