Algorithm

A. Find The Array
time limit per test
1 second
memory limit per test
256 megabytes
Problem link- https://codeforces.com/problemset/problem/1550/A
input
standard input
output
standard output

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

For example:

  • the array [5,3,1][5,3,1] is beautiful: for a1�1, the number a1−2=3�1−2=3 exists in the array; for a2�2, the number a2−2=1�2−2=1 exists in the array; for a3�3, the condition a3=1�3=1 holds;
  • the array [1,2,2,2,2][1,2,2,2,2] is beautiful: for a1�1, the condition a1=1�1=1 holds; for every other number ai��, the number ai−1=1��−1=1 exists in the array;
  • the array [1,4][1,4] is not beautiful: for a2�2, neither a2−2=2�2−2=2 nor a2−1=3�2−1=3 exists in the array, and a2≠1�2≠1;
  • the array [2][2] is not beautiful: for a1�1, neither a1−1=1�1−1=1 nor a1−2=0�1−2=0 exists in the array, and a1≠1�1≠1;
  • the array [2,1,3][2,1,3] is beautiful: for a1�1, the number a1−1=1�1−1=1 exists in the array; for a2�2, the condition a2=1�2=1 holds; for a3�3, the number a3−2=1�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≤t≤50001≤�≤5000) — the number of test cases.

Then t� lines follow, the i�-th line contains one integer s� (1≤s≤50001≤�≤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�.

Example
input
Copy
4
1
8
7
42
output
Copy
1
3
3
7
Note

Consider the example test:

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

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;


#define ll long long
#define endl '\n'
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int t;
  cin>>t;
  while(t--){
    double n;
    cin>>n;
    cout<<ceil(sqrt(n))<<endl;
  }

}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
4
1
8
7
42

Output

x
–
+
cmd
1
3
3
7
Advertisements

Demonstration

Codeforcess Solution 1550-A A. Find The Array ,C++, Java, Js and Python,1550-A,Codeforcess Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+