Codeforces Round 530 (Div. 2) |
---|
Закончено |
Маленькая София учится в четвертом классе. Сегодня на уроке геометрии она узнала про отрезки и квадраты. По пути домой она решила нарисовать на снегу $$$n$$$ квадратов со стороной длины $$$1$$$. Для простоты будем считать, что София живёт на плоскости и может рисовать только отрезки длины $$$1$$$, параллельные осям координат, с вершинами в целых точках.
Для того, чтобы нарисовать отрезок, София поступает следующим образом. Пусть она хочет нарисовать вертикальный отрезок с координатами концов $$$(x, y)$$$ и $$$(x, y+1)$$$. Тогда София смотрит, существует ли уже нарисованный отрезок с координатами концов $$$(x', y)$$$ и $$$(x', y+1)$$$ для какого-нибудь $$$x'$$$. Если такой отрезок существует, то София быстро рисует новый отрезок, используя старый, как ориентир. Если же такого отрезка нет, то Софии приходится брать линейку и долго отмерять новый отрезок. Аналогично София поступает для горизонтальных отрезков, но только теперь она проверяет существование отрезка с такими же координатами $$$x$$$, $$$x+1$$$ и различающейся координатой $$$y$$$.
Например, если Софии надо нарисовать один квадрат, ей придется нарисовать два отрезка с помощью линейки:
После этого можно нарисовать оставшиеся два отрезка, используя первые в качестве ориентира:
Если же Софии надо нарисовать два квадрата, ей придется нарисовать три отрезка с помощью линейки:
После этого можно нарисовать оставшиеся четыре отрезка, используя первые в качестве ориентира:
София торопится домой, поэтому хочет минимизировать число отрезков, которые ей придется рисовать с линейкой без ориентира. Помогите ей найти это минимальное число.
Единственная строка входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^{9}$$$) — количество квадратов, которое София хочет нарисовать.
Выведите одно число — минимальное число отрезков, которые Софии придется рисовать с линейкой без ориентира, чтобы нарисовать $$$n$$$ единичных квадратов описанным выше способом.
1
2
2
3
4
4
Название |
---|