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
hide comments
js2072:
2016-06-28 16:48:30
what is the answer for case 0?
|
|
Piyush Kumar:
2016-06-20 20:00:43
Moved to tutorial! |
|
Francky:
2016-06-20 17:38:23
@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...
|
|
[Lakshman]:
2016-06-20 16:52:30
I used sys.stdin and my solution is log(sqrt(n)) still got AC with python 2.7 and 3.4.
|
|
Siddharth Singh:
2016-06-20 09:46:37
can anyone tell me the outputs for
|
|
Francky:
2016-06-20 01:03:52
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 !
|
|
wisfaq:
2016-06-19 22:03:09
Nice problem.
|
|
meettaraviya:
2016-06-19 13:13:00
test case 3 is wrong as @Francky said
|
|
Francky:
2016-06-19 12:28:04
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.
|
|
Piyush Kumar:
2016-06-19 12:09:28
If the constraints are too tight, I will consider making an easier version as well. |
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 |