All Tracks Basic Programming Implementation Basics of Implementation Problem

Fredo is in a Hurry

Ad-Hoc, Basic Programming, Easy


Fredo lives in a building with \(N+1\) floors and his apartment is at floor N. The floors are numbered from 0 to N, N being the highest floor. Fredo has just come from school and is at floor 0. His favourite anime is about to start and he wants to reach his apartment as soon as possible.
He can either use staircase or elevator or a combination of both (use staircase for x floors and cover rest floors by elevator) to reach his apartment.

  • If he uses staircase, he takes f amount of time to reach floor f from floor \(f-1\).
  • Elevator takes 1 unit time to go from any floor to it's neighbouring floors.

The elevator currently is coming down from floor N .The elevator stops at the floor where the elevator button is pressed .From this floor, the elevator goes to floor N .
Tell him what is the minimum time he needs to reach floor N from floor 0.

Assumptions: Only Fredo uses the elevator during that period of time. Fredo will press the elevator button atmost once. If Fredo presses the elevator button at floor x, then the elevator needs to be at a floor \(\ge x\).

Input Format:
The first line consists of an integer T denoting the number of test cases.
The only line of each test consists of an integer N denoting the number of floors.

Output Format:
For each test case, print the minimum time Fredo needs to reach floor N from floor 0 in a separate line.

Input Constraints:
\(1 \le T \le 1000\)
\(1 \le N \le 10^9\)


Test case 1:
Fredo reaches 1st floor from floor 0 in 1 unit time. At this time, he presses the elevator button and the elevator stops there as it was also at that floor (because the elevator had started coming downwards the moment Fredo started to take the staircase, so in 1 unit of time, Fredo and elevator both reach floor 1). Then , he uses elevator to go to the second floor from 1st floor which also takes 1 unit of time.
So, answer= 1 + 1

Test case 2:
N = 6
Fredo reaches floor 2 at time = 3 (because he takes 1 unit of time for 1st floor and 2 units of time for 2nd floor when using staircase).
Elevator also reaches floor 2 at time 4. (Fredo waits for 1 unit of time at floor 2).
Then elevator reaches floor 6 from floor 2 in 4 units of time.
Fredo takes the elevator from this floor. So , total time = 4 + 4 =8

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

November Circuits

View All Notifications