Find The Array Codeforces Solution

by

Find The Array Codeforces Solution

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

For example:

  • the array [5,3,1][5,3,1] is beautiful: for a1a1, the number a1−2=3a1−2=3 exists in the array; for a2a2, the number a2−2=1a2−2=1 exists in the array; for a3a3, the condition a3=1a3=1 holds;
  • the array [1,2,2,2,2][1,2,2,2,2] is beautiful: for a1a1, the condition a1=1a1=1 holds; for every other number aiai, the number ai−1=1ai−1=1 exists in the array;
  • the array [1,4][1,4] is not beautiful: for a2a2, neither a2−2=2a2−2=2 nor a2−1=3a2−1=3 exists in the array, and a2≠1a2≠1;
  • the array [2][2] is not beautiful: for a1a1, neither a1−1=1a1−1=1 nor a1−2=0a1−2=0 exists in the array, and a1≠1a1≠1;
  • the array [2,1,3][2,1,3] is beautiful: for a1a1, the number a1−1=1a1−1=1 exists in the array; for a2a2, the condition a2=1a2=1 holds; for a3a3, the number a3−2=1a3−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 ss.Input

The first line contains one integer tt (1≤t≤50001≤t≤5000) — the number of test cases.

Then tt lines follow, the ii-th line contains one integer ss (1≤s≤50001≤s≤5000) for the ii-th test case.Output

Print tt integers, the ii-th integer should be the answer for the ii-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][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.

Solution

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        int s;
        cin >> s;
        int tmp = 1, sum = 1;
        int ans = 1;
        while(sum < s) {
            tmp += 2;
            sum += tmp;
            ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

Educational Codeforces Round 111 (Rated for Div. 2)

Leave a Comment