Find The Array (Codeforces 1550A)
Tags: Math, greedy

Let's call an array $$$a$$$ consisting of $$$n$$$ positive (greater than $$$0$$$) integers beautiful if the following condition is held for every $$$i$$$ from $$$1$$$ to $$$n$$$: either $$$a_i = 1$$$, or at least one of the numbers $$$a_i - 1$$$ and $$$a_i - 2$$$ exists in the array as well.For example:   the array $$$[5, 3, 1]$$$ is beautiful: for $$$a_1$$$, the number $$$a_1 - 2 = 3$$$ exists in the array; for $$$a_2$$$, the number $$$a_2 - 2 = 1$$$ exists in the array; for $$$a_3$$$, the condition $$$a_3 = 1$$$ holds;  the array $$$[1, 2, 2, 2, 2]$$$ is beautiful: for $$$a_1$$$, the condition $$$a_1 = 1$$$ holds; for every other number $$$a_i$$$, the number $$$a_i - 1 = 1$$$ exists in the array;  the array $$$[1, 4]$$$ is not beautiful: for $$$a_2$$$, neither $$$a_2 - 2 = 2$$$ nor $$$a_2 - 1 = 3$$$ exists in the array, and $$$a_2 \ne 1$$$;  the array $$$[2]$$$ is not beautiful: for $$$a_1$$$, neither $$$a_1 - 1 = 1$$$ nor $$$a_1 - 2 = 0$$$ exists in the array, and $$$a_1 \ne 1$$$;  the array $$$[2, 1, 3]$$$ is beautiful: for $$$a_1$$$, the number $$$a_1 - 1 = 1$$$ exists in the array; for $$$a_2$$$, the condition $$$a_2 = 1$$$ holds; for $$$a_3$$$, the number $$$a_3 - 2 = 1$$$ exists in the array. You are given a positive integer $$$s$$$. Find the minimum possible size of a beautiful array with the sum of elements equal to $$$s$$$.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases.Then $$$t$$$ lines follow, the $$$i$$$-th line contains one integer $$$s$$$ ($$$1 \le s \le 5000$$$) for the $$$i$$$-th test case.

Output: Print $$$t$$$ integers, the $$$i$$$-th integer should be the answer for the $$$i$$$-th testcase: the minimum possible size of a beautiful array with the sum of elements equal to $$$s$$$.

Note: Consider the example test:  in the first test case, the array $$$[1]$$$ meets all conditions;  in the second test case, the array $$$[3, 4, 1]$$$ meets all conditions;  in the third test case, the array $$$[1, 2, 4]$$$ meets all conditions;  in the fourth test case, the array $$$[1, 4, 6, 8, 10, 2, 11]$$$ meets all conditions. 

Sample Inputs:
4
1
8
7
42

Sample Outputs:
1
3
3
7

Solution (Python):
for s in [*open(0)][1:]:
    print(int((int(s) - 1) ** 0.5) + 1)

Solution (Python):
from math import ceil
for s in [*open(0)][1:]:
    s = int(s)
    print(int(ceil(s ** 0.5)))

Solution (Python):
from math import *
for s in [*open(0)][1:]:
    print(ceil(sqrt(int(s))))