| Codeforces Round 833 (Div. 2) |
|---|
| Закончено |
У вас есть $$$n$$$ прямоугольных деревянных блоков, пронумерованных целыми числами от $$$1$$$ до $$$n$$$. Высота и длина $$$i$$$-го из них равны $$$1$$$ и $$$\lceil \frac{i}{2} \rceil$$$ соответственно.
Здесь $$$\lceil \frac{x}{2} \rceil$$$ обозначает результат деления $$$x$$$ на $$$2$$$, округлённый вверх. Например, $$$\lceil \frac{4}{2} \rceil = 2$$$ и $$$\lceil \frac{5}{2} \rceil = \lceil 2.5 \rceil = 3$$$.
Например, если $$$n=5$$$, то у вас если блоки размеров $$$1 \times 1$$$, $$$1 \times 1$$$, $$$1 \times 2$$$, $$$1 \times 2$$$ и $$$1 \times 3$$$.
Доступные блоки при $$$n=5$$$ Вы хотите создать большой квадрат, используя эти блоки и не поворачивая их. Какая максимальная длина стороны может быть у такого квадрата? Обратите внимание, что вы не обязаны использовать все блоки.
Один из способов создать квадрат $$$3 \times 3$$$, используя блоки с номерами от $$$1$$$ до $$$5$$$ В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания этих наборов.
В первой строке дано одно число $$$n$$$ ($$$1 \le n \le 10^9$$$) — количество блоков.
Для каждого набора входных данных выведите одно число: максимальную длину стороны квадрата, такого что его возможно собрать из имеющихся блоков.
325197654321
1 3 98827161
В первом наборе входных данных достаточно использовать один блок, чтобы создать квадрат $$$1 \times 1$$$.
Один из способов создать квадрат $$$3 \times 3$$$ во втором наборе входных данных приведён в условии. Можно показать, что невозможно создать квадрат $$$4 \times 4$$$ или больших размеров, поэтому ответ равен $$$3$$$.
