CF1550A Find The Array（贪心算法）

Let's call an array a  consisting of nn positive (greater than 00) integers beautiful if the following condition is held for every ii from  1 to  n: either ai=1  or at least one of the numbers ai−1  and ai−2  exists in the array as well.

For example:

• the array [5,3,1] is beautiful: for a1 , the number a1−2=3 exists in the array; for  a2, the number a2−2=1 exists in the array; for  a3, the condition a3=1 holds;
• the array [1,2,2,2,2] is beautiful: for  a1, the condition a1=1  holds; for every other number  ai, the number ai−1=1  exists in the array;
• the array [1,4]  is not beautiful: for a2 , neither a2−2=2  nor a2−1=3  exists in the array, and  a2≠1;
• the array [2]  is not beautiful: for a1 , neither  a1−1=1 nor  a1−2=0 exists in the array, and a1≠1
• the array [2,1,3] is beautiful: for a1 , the number a1−1=1  exists in the array; for  a2, the condition a2=1  holds; for  a3, the number a3−2=1  exists in the array.

You are given a positive integer ss. 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≤t≤5000 ) — the number of test cases.

Then t lines follow, the i-th line contains one integer  s (1≤s≤5000 ) for the  i-th test case.

Output

Print tt 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 ss.

Example

Input

4

1

8

7

42

Output

1

3

3

7

Note

Consider the example test:

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

题目分析就是我们

一个数组 a 是好的当且仅当数组内每一个数  ai 满足：  ai=1 或   ai−1=aj 或  ai−2=aj 。

给出一个好数组的元素之和 x  ，求好数组的元素个数最小值。  

思路

本题用贪心做，每次放的数尽量大，即每个数比前一个数多 2  。如果最后一个数放不下，那么就把最后一个数减小到刚好放下，元素个数不变。

具体实现看代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int t;
  cin>>t;
  while(t--)
  {
    int n,sum1=0,sum2=0;
    cin>>n;
    for(int i=1;i<=500000;i+=2)
    {
      sum1+=i;
      sum2++;
    if(sum1>=n)
    {
      cout<<sum2<<endl;
      break;
    }
    }
  }
}