Logo C++ Online Judge

C++

时间限制:1 s 空间限制:512 MB
TA: 苏凯
Statistics

We have $n$ signal towers arranged in a row, with each tower $i$ located at coordinate $x_i$. We are also equipped with $m$ signal boosters that can be installed on select towers. Our goal is to minimize the maximum distance between any tower and its nearest signal booster. Please output an optimal plan for placing the signal boosters on the towers.

The distance between $x_i$ and $x_{i-1}$ is $x_i-x_{i-1}=$i^(i>>1) in C, which corresponds to the Gray Code. This code is a binary numeral system used in digital communication to prevent race conditions. It's important to note that we define $x_0=0$, although there is no tower at this position. Hence, $x_1$ is set to 1.

Input: Two integers $n,m$ separated by a single space.

Output: $m$ integers separated by spaces, indicating the $x$-coordinates of the towers to place the signal boosters.

Constraints: It is guaranteed that $1\le m\le n$ and $x_n\le 2^{31}-1$.

Example Input

3 1

Example Output

4

The positions of the towers are $1,4,6$. We could only place one signal booster, so putting it at $x=4$ is the optimal plan, with the maximum distance being $4-1=3$.

Hint

Checkout problem 4 first!