J. Чудовищная экономия
Задачу добавил: alef
Успешно сдано решений: 35
На досуге Программист играет в одну игру, которую сам же и написал.
В этой игре есть два монстра:
Большой Линейный Монстр. Каждый его удар уменьшает здоровье героя на 100500. Чтобы убить его, герою требуется нанести ему 11 ударов;
Большой Логарифмический Монстр. Каждый его удар делит здоровье героя на 2 с округлением вниз до ближайшего целого. Чтобы убить его, герою также необходимо нанести ему 11 ударов.
Один раз в час здоровье героя полностью восстанавливается, и он отправляется сражаться с монстрами. Бой происходит так: сначала игрок выбирает любого из монстров и ударяет его. После этого монстры наносят игроку удары в следующем порядке: сначала Большой Логарифмический Монстр (если он еще жив), а потом Большой Линейный Монстр (если он еще жив). Бой повторяется, пока не будет повержен герой или оба монстра. Как и всегда, герой или монстр считается поверженным, если его здоровье перестает быть положительным.
Однажды монстрам надоело, что их постоянно убивают. Некарат, старый знакомый Большого Логарифмического Монстра, оказался слишком занят умножением игроков на ноль в четвертом акте. Монстры посовещались между собой и решили купить в магазине артефактов адскую линейку сокрушения, которая увеличивает повреждения, наносимые Большим Линейным Монстром. Они хотят, чтобы они оба гарантированно выжили в сражении с героем, здоровье которого равно H. В магазине продаются разные линейки, при этом чем большую прибавку урона дает линейка, тем дороже она стоит. Монстры очень экономны, и хотят приобрести наименее дорогую линейку, которая позволит им решить их проблему.
Ваша задача — определить минимальное значение для прибавки урона, который должна обеспечить такая линейка.
В первой строке содержится единственное целое число H (205624024 ≤ H ≤ 1018) — здоровье героя, который отправляется сражаться с монстрами.
В первой строке выведите единственное целое число — минимально возможное значение для прибавки урона, которое позволит монстрам выжить в сражении.
205624024
1
1000000000000000000
488758553174182