Квадратный апгрейд

В игре есть апгрейд «Квадратный щит». Если у тебя есть x кристаллов, то можно поставить щит уровня k, только если хватает на квадрат: нужно k² ≤ x кристаллов.

Помоги выбрать максимальный уровень щита.

Важно: x может быть очень большим (как на олимпиадах, больше 32-битного int).

Формат ввода

Одно целое число x.

Формат вывода

Выведите одно целое число k — максимальное, для которого k² ≤ x.

Ограничения

• 0 ≤ x ≤ 10^18

Пример

Ввод:

10

Вывод:

3

Ключевое наблюдение: условие k*k ≤ x монотонно по k. Если для некоторого k хватает кристаллов, то для всех меньших уровней тоже хватит. Значит, можно искать границу «хватает / не хватает» бинарным поиском.

Почему не просто int(sqrt(x))? При больших x и вещественных числах можно получить ошибку из‑за округления. Целочисленный бинарный поиск работает точно.

План:

• Прочитай x (это может быть до 10^18, в Python int справится).
• Задай границы для k. Минимум l = 0. Максимум можно взять r = 10^9, потому что (10^9)^2 = 10^18, а больше при данных ограничениях не нужно.
• Пока l < r:
• Возьми середину с округлением вверх: m = (l + r + 1) // 2.
• Если m*m ≤ x, то m подходит, сдвигаем левую границу: l = m.
• Иначе m слишком большой, сдвигаем правую: r = m - 1.
• Ответ — l (он же r).

Сложность: O(log r), здесь около 30 шагов.

Частая ошибка: брать середину как (l + r) // 2 и при обновлении l = m зациклиться, когда l+1 = r. Лечится формулой с +1 (середина вверх) или другим аккуратным вариантом обновления границ.