Increase and Copy
Hazrat Ali
In one move, you can do one of the following things:
- Increase some (single) element of a by 1 (choose some i from 1 to the current length of a and increase ai by one);
- 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 ai to the end of the array).
For example, consider the sequence of five moves:
- You take the first element a1, append its copy to the end of the array and get a=[1,1].
- You take the first element a1, increase it by 1 and get a=[2,1].
- You take the second element a2, append its copy to the end of the array and get a=[2,1,1].
- You take the first element a1, append its copy to the end of the array and get a=[2,1,1,2].
- You take the fourth element a4, increase it by 1 and get a=[2,1,1,3].
Your task is to find the minimum number of moves required to obtain the array with the sum at least n.
You have to answer t independent test cases.
The first line of the input contains one integer t (1≤t≤1000) — the number of test cases. Then t test cases follow.
The only line of the test case contains one integer n (1≤n≤109) — the lower bound on the sum of the array.
For each test case, print the answer: the minimum number of moves required to obtain the array with the sum at least n.
5 1 5 42 1337 1000000000
0 3 11 72 63244
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
int ans = 2 * sqrt(n) - 1;
int rn = sqrt(n);
if (rn * rn == n)
{
ans--;
}
cout << ans << endl;
}
return 0;
}