1426C.md (1784B)
1 Source: https://codeforces.com/problemset/problem/1426/C 2 3 C. Increase and Copy 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Initially, you have the array $a$ consisting of one element $1$ ($a = [1]$). 22 23 In one move, you can do one of the following things: 24 25 * Increase some (single) element of $a$ by $1$ (choose some $i$ from $1$ to the current length of $a$ and increase $a_i$ by one); 26 * Append the copy of some (single) element of $a$ to the end of the array (choose some $i$ from $1$ to the current length of $a$ and append $a_i$ to the end of the array). 27 28 For example, consider the sequence of five moves: 29 30 1. You take the first element $a_1$, append its copy to the end of the array and get $a = [1, 1]$. 31 2. You take the first element $a_1$, increase it by $1$ and get $a = [2, 1]$. 32 3. You take the second element $a_2$, append its copy to the end of the array and get $a = [2, 1, 1]$. 33 4. You take the first element $a_1$, append its copy to the end of the array and get $a = [2, 1, 1, 2]$. 34 5. You take the fourth element $a_4$, increase it by $1$ and get $a = [2, 1, 1, 3]$. 35 36 Your task is to find the minimum number of moves required to obtain the array with the sum at least $n$. 37 38 You have to answer $t$ independent test cases. 39 40 Input 41 42 The first line of the input contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then $t$ test cases follow. 43 44 The only line of the test case contains one integer $n$ ($1 \le n \le 10^9$) — the lower bound on the sum of the array. 45 46 Output 47 48 For each test case, print the answer: the minimum number of moves required to obtain the array with the sum at least $n$. 49 50 Example 51 52 Input 53 54 ``` 55 5 56 1 57 5 58 42 59 1337 60 1000000000 61 ``` 62 63 Output 64 65 ``` 66 0 67 3 68 11 69 72 70 63244 71 ```