SPOJ.com - Problem VECTAR2

VECTAR2 - Changus Big Battle

This version has been moved to tutorial section.

You can access the classical version here: Changus Final Battle : http://www.spoj.com/problems/VECTAR4/

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 <= N <= 10^9

1 <= T <= 5*10^5

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

Submit solution!

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

hide comments

2016-06-28 16:48:30
what is the answer for case 0?
Re: Look at the constraints carefully, there is no case 0 !

Last edit: 2016-06-28 18:55:53

2016-06-20 20:00:43 Piyush Kumar
Moved to tutorial!

2016-06-20 17:38:23 Francky
@psetter : If you want to allow only O(1), even for slow languages, then maybe you should consider increase constraints on N. What about N<10^18 ? Only an idea...

Re: I can do that, the only problem being the already AC solutions. (25 currently). I will have to rejudge them, that will lead to WAs mostly .

=(Francky)=> You can wait for another advice ; but I would put this one to tutorial, and create a new problem with constraints N<10^18, and if possible TL that allows AC with slow language and basic IO. With a new problem : no rejudge, no WA... Many thanks for your implies.

Re: Will do that, thanks for the advice! :)

Last edit: 2016-06-20 19:26:36

2016-06-20 16:52:30 [Lakshman]
I used sys.stdin and my solution is log(sqrt(n)) still got AC with python 2.7 and 3.4.
=> The original purpose of this question was to pass only O(1) solutions. I don't know what to do with slower languages -_-

Last edit: 2016-06-20 17:11:46

2016-06-20 09:46:37 Siddharth Singh
can anyone tell me the outputs for
3
101
275
9874

2016-06-20 01:03:52 Francky
O(1) don't pass TL using decent PY3.4 code ; please consider update time limit. O(sqrt(n)) with fast language won't pass !

Re: wisafq and some other users got AC in python with decent codes. I will increase the TL a little anyway :)
Re:TL has been updated!

=(Francky)=> With basic IO, it's still TLE, I used faster IO to get AC with PY3.4...

Re: I have relaxed the TL a bit more. Basic IO should now pass in Python!

=(Francky)=> Thanks for that, but it seems it allows bad complexity codes...

Last edit: 2016-06-20 17:39:30

2016-06-19 22:03:09 wisfaq
Nice problem.
Python can get AC.
However, I was glad the tutorial version existed.

Re: Glad you liked it:) The tutorial version will pass O(sqrt(n)) solution while this one won't!

Last edit: 2016-06-19 22:18:23

2016-06-19 13:13:00
test case 3 is wrong as @Francky said
Re: The problem statement was updated! 'He starts on day 1 by x=1, i.e. killing one enemy.' Please read the description carefully!

Last edit: 2016-06-19 13:17:55

2016-06-19 12:28:04 Francky
According to case 3 : the first day, one kill is a constraint ; otherwise 3+3+2+1 would be a one day less battle. Please fix description.
I don't think an easier edition is need, unless a python (eg of slow language) is unable to have AC with decent code.

Re: My bad! Fixed the description. I have added an easier version. Will move it to tutorial!

Last edit: 2016-06-19 12:36:53

2016-06-19 12:09:28 Piyush Kumar
If the constraints are too tight, I will consider making an easier version as well.