VECTAR4 - Changus Final Battle

Try the tutorial version first :  Changus Big Battle :  http://www.spoj.com/problems/VECTAR2/

Changu is going to fight a battle. He is powerful but he has a few limitations. If he kills x enemies on a particular day, then he can only kill x-1 or x or x+1 enemies on the next day. And also, he can kill no more than 1 enemy on the last day of battle. Given N, the number of enemies he has to kill to end the battle, you have to calculate the minimum number of days required for Changu to finish the battle, keeping in mind his limitations. He starts on day 1 by x=1, i.e. killing one enemy.

Input

The first line contains an integer T denoting the number of test cases.

Each of the next T lines contain an integer N.

Output

T lines : Minimum number of days required for each test case.

Constraints

1 <= T <= 10^5

1 <= N <= 10^18

Example

Input:
3
4
1
9

Output:
3
1
5

Explanation

Case 1 : 1 + 2 + 1

Case 2 : 1

Case 3 : 1 + 2 + 3 + 2 + 1

 

Note: Test files have been updated. Solutions will be rejudged.


Added by:Piyush Kumar
Date:2016-06-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2018-06-28 05:02:10
OMG ! first time I got 5th position ! Damn Happy ! 0.02 sec!
2017-11-05 22:09:55
According to Python, sqrt(999999999999999936) = 1000000000. Annoying.
2017-01-13 18:21:11
in vectar2 1st I got TLE but thinking deeply got AC in both question same code !!! Nice one O(1),yes:)
2016-10-07 22:21:19
Are the testcases weak ? I mean VECTAR2 is the tutorial problem with the same question but smaller constraints and my solution for VECTAR2 runs faster than that for VECTAR4, which is essentially the same code except for replacing int by long long . Anyways nice question. Made me think for a while. O(1) it is :)

Last edit: 2016-10-07 22:22:10
2016-07-28 10:09:33 cegprakash
Weak test cases. Worst case inputs are not in input file. My initial very bad code passed too!

Input : 1000000000000000000
Expected : 1999999999
My ACC result : 1000000000000000000

Re: Actually the test cases are way off the boundary. I will update the files and rejudge. Thanks.

Last edit: 2016-07-28 15:04:06
2016-07-27 21:29:42
@Piyush Kumar please remove spoiler comments.

Re: Thanks. Done that.

Last edit: 2016-07-28 15:00:42
2016-07-08 10:29:19
<spoiler removed>

Last edit: 2016-07-28 15:01:16
2016-07-02 21:59:18
nice problem..<3..
<spoiler removed>

Last edit: 2016-07-28 14:59:01
2016-06-26 02:59:20
@tarungupta1956: me too :P +1/-1 in wrong order :P and I was looking for mistake for 15 minutes :P
2016-06-22 20:22:04
took me 10 wa to realize a stupid mistake\:

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.