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.
First line contains T (1<=T<=10) number test cases. Each test case consist of 1 integer K (2<=K<=10^18),
minimum number of student required.
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)
wow! looked like dp but a deeper thought gives u a nice logic! totally adhoc ques.. :)
what the hell :D ! nice ;)
really good one :)
Solved this as my 100th classical one :)
what is the output for 10^18 ?? ... getting WA
(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
nice problem ;-)
@sourabh singh: i assumed it to be integer division.
@dce coder forn/2 we nid to use floor ceilLast edit: 2012-03-02 14:11:17