hackercupai/hackercup

1You are racing on a 2D lattice grid starting from the origin (0,0) towards a2goal (M,N) where M and N are positive integers such that **0< M ≤ N**. There3is a checkpoint that's neither on the origin nor on the goal with coordinates4(m,n) such that **0 ≤ m ≤ M** and **0 ≤ n ≤ N**. You must clear the checkpoint5before you reach the goal. The shortest path takes **T = M + N** steps.6 7At each point, you can move to the four immediate neighbors at a fixed speed,8but since you don't want to lose the race, you are only going to take either a9step to the right or to the top.10 11Even though there are many ways to reach the goal while clearing the12checkpoint, the race is completely pointless since it is relatively easy to13figure out the shortest route. To make the race more interesting, we change14the rules. ** Instead of racing to the same goal **(M,N)**, the racers get to15pick a goal **(x,y)** and place the checkpoint to their liking so that there16are exactly **S** distinct shortest paths. **17 18For example, given **S = 4**, consider the following two goal and checkpoint19configurations20 21* **Placing the checkpoint at (1, 3) and the goal at (2,3). ** There are 4 ways to get from the origin to the checkpoint depending on when you move to the right. Once you are at the checkpoint, there is only one way to reach the goal with minimal number of steps. This gives a total of 4 distinct shortest paths, and takes **T = 2 + 3 = 5** steps. However, you can do better. 22* **Placing the checkpoint at (1, 1) and the goal at (2,2). ** There are two ways to get from the origin to the checkpoint depending on whether you move to the right first or later. Similarly, there are two ways to get to the goal, which gives a total of 4 distinct shortest paths. This time, you only need **T = 2 + 2 = 4** steps. 23 24As a Hacker Cup racer, you want to figure out how to place the checkpoint and25the goal so that you cannot possibly lose. **Given S, find the smallest26possible T, over all possible checkpoint and goal configurations, such that27there are exactly S distinct shortest paths clearing the checkpoint.**28 29### Input30 31As input for the race you will receive a text file containing an integer32**R**, the number of races you will participate in. This will be followed by33**R** lines, each describing a race by a single number **S**.  34  35 36### Output37 38Your submission should contain the smallest possible length of the shortest39path, **T** for each corresponding race, one per line and in order.  40  41 42### Constraints43 445 ≤ **R** ≤ 20  451 ≤ **S** ≤ 10,000,000  46 47