P9948 [USACO20JAN] Race B

Bessie is participating in a $K$ ($1\le K\le 10^9$) meter running race. She starts the race at a speed of $0$ meters per second. During each second, she can choose to increase her speed by $1$ meter per second, keep her speed the same, or decrease her speed by $1$ meter per second. For example, in the first second, she can increase her speed to $1$ meter per second and run $1$ meter, or keep her speed at $0$ meters per second and run $0$ meters. Bessie's speed will never drop below zero. Bessie always runs toward the finish line, and she wants to finish the race in an integer number of seconds. Also, she does not want to be running too fast at the finish: at the moment when Bessie completes $K$ meters, she wants her speed to be at most $X$ ($1\le X\le 10^5$) meters per second. For $N$ ($1\le N\le 1000$) different values of $X$, Bessie wants to know how fast she can finish the race.

The first line of input contains two integers $K$ and $N$. Each of the next $N$ lines contains one integer $X$.

Output $N$ lines. Each line contains one integer: the minimum time needed for Bessie to run $K$ meters while having a finishing speed less than or equal to $X$.

### Sample Explanation 1 When $X=1$, one optimal plan is: 1. Increase speed to $1$ m/s, run $1$ meter. 2. Increase speed to $2$ m/s, run $2$ meters, for a total of $3$ meters. 3. Keep speed at $2$ m/s, for a total of $5$ meters. 4. Keep speed at $2$ m/s, for a total of $7$ meters. 5. Keep speed at $2$ m/s, for a total of $9$ meters. 6. Decrease speed to $1$ m/s, for a total of $10$ meters. When $X=3$, one optimal plan is: 1. Increase speed to $1$ m/s, run $1$ meter. 2. Increase speed to $2$ m/s, for a total of $3$ meters. 3. Increase speed to $3$ m/s, for a total of $6$ meters. 4. Keep speed at $3$ m/s, for a total of $9$ meters. 5. Keep speed at $3$ m/s, for a total of $12$ meters. Note that when $X=3$, the following plan is not valid: 1. Increase speed to $1$ m/s, run $1$ meter. 2. Increase speed to $2$ m/s, for a total of $3$ meters. 3. Increase speed to $3$ m/s, for a total of $6$ meters. 4. Increase speed to $4$ m/s, for a total of $10$ meters. This is because at the moment Bessie completes $10$ meters, her speed is $4$ m/s. Translated by ChatGPT 5