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

Задача . Автомобиль "Пантера"


Однажды утром Глеб с ужасом осознал, что проспал, а пары в «Высшем университете» начинаются уже скоро. Опоздать было бы не так страшно, если бы он их и не вёл. К счастью, автомобиль Глеба «Пантера» довольно мощный: для упрощения будем считать, что за одну секунду он может сначала или увеличить скорость на 1, или уменьшить скорость на 1, или не менять её, а после этого его автомобиль проезжает x метров, где x - его текущая скорость в метрах в секунду. Потом он снова принимает решение об изменении скорости. Начальная скорость автомобиля преподавателя в момент, когда он только выезжает из дома, равна нулю. Путь до университета от его дома не близкий: нужно проехать d метров.

Глеб, обеспокоенный за знания своих студентов, хочет попасть в университет как можно раньше, чтобы успеть подготовиться к проведению лекции. К сожалению, на проезде на парковку университета установлен шлагбаум, поэтому скорость автомобиля после того, как он проехал ровно d метров должна быть равна 0.

Пока Глеб собирался на работу, его заинтересовал вопрос, а за какое минимальное время он может доехать до работы, если будет действовать оптимально. Так как преподаватель будет занят скоростным вождением, ответить на этот вопрос честь выпала вам!



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

Вводится одно целое число - d (1 <= d <= 1018), расстояние до университета.

Обратите внимание, что входные данные могут быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.


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

Примечание

В первом тесте из условия Глебу выгодно действовать следующим образом:

  1. Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
  2. Не менять скорость, проехать один метр; скорость 1 м/с, проехал 2 метра от дома.
  3. Уменьшить скорость на один; скорость 0 м/с, проехал 2 метра от дома.

Таким образом, он потратит 3 секунды, и его конечная скорость будет равно 0 м/с.

Во втором тесте из условия Глебу выгодно действовать, например, так:

  1. Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
  2. Увеличить скорость на один, проехать два метра; скорость 2 м/с, проехал 3 метра.
  3. Увеличить скорость на один, проехать три метра; скорость 3 м/с, проехал 6 метров.
  4. Уменьшить скорость на один, проехать два метра; скорость 2 м/с, проехал 8 метров.
  5. Уменьшить скорость на один, проехать один метр; скорость 1 м/с, проехал 9 метров.
  6. Не менять скорость, проехать один метр; скорость 1 м/с, проехал 10 метров.
  7. Уменьшить скорость на один; скорость 0 м/с, проехал 10 метров.

     

Таким образом, он потратит 7 секунд, и его конечная скорость будет равно 0 м/с.

 
Примеры
Входные данные Выходные данные
1
2
3
2
10
7



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

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