DCEPC202 - Unique Paths

Vaibhav sir and Jyoti ma’am are pretty pissed off after taking the doubt clearing session for first batch. People are not taking them seriously and doing their assignments, so they decided only intelligent students should appear in the tutorials. So they put up a condition, only those students who came to the class walking on unique paths can attend the class. By unique path they meant that at least 1 move differs from any other path. You are at the position (0, 0) in the corridor and the class is at the position (n-1, 4). Where n is the length of corridor and width is 5 units. You can move only to the adjacent tile on the floor. As you are not idiots you have to reach at the class using shortest path only. Corridor has some broken tiles which are not to be traversed on, they are : (0, 2), (n/2, 0), (n/2, 2), (n/2, 4) and (n-1, 2). The minimum students required for class is given (k). You have to tell the minimum length of corridor to select k students.

Input

First line contains T (1 <= T <= 10) number test cases. Each test case consist of 1 integer K (2 <= K <= 1018), the minimum number of student required.

Output

Minimum length of corridor required to select at least K student.

Note : Required length of the corridor will always be between 4 and 10000 (inclusive)

Example

Input:
2
2
9

Output: 4
6

Added by:dce coders
Date:2012-02-26
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2015-10-25 00:13:18 hardik agrawal
wow! looked like dp but a deeper thought gives u a nice logic! totally adhoc ques.. :)
2015-06-23 09:57:57 Rishav Goyal
what the hell :D ! nice ;)

seriously pissed off

Last edit: 2015-06-23 09:58:29
2014-08-31 00:25:56 Akshay Deep
really good one :)
2012-12-16 08:39:43 triveni
Solved this as my 100th classical one :)
2012-07-18 10:24:11 RAHUL KUMAR
what is the output for 10^18 ?? ... getting WA
2012-06-01 16:31:45 (Tjandra Satria Gunawan)(曾毅昆)
nice problem ;-)
2012-03-07 20:35:33 Sidharth Gupta
@sourabh singh: i assumed it to be integer division.
2012-03-02 12:54:06 Sourabh Singh
@dce coder forn/2 we nid to use floor ceil

Last edit: 2012-03-02 14:11:17
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.