Limits
4s, 512 MB

The numbers $1,2,3, \cdots n$ (each integer from $1$ to $n$ once) are written on a board. In one operation, Jesse can choose any number $x$ from the board and replace it by $\lfloor \frac{x}{2} \rfloor$(Half of $x$ rounded down). Jesse wants to minimize the sum of the integers after performing exactly $k$ operations. Help Jesse.

The first line contains $T (1 \leq T \leq 10^5)$, the number of testcases.

Each of the following $T$ lines contain two space separated integers, $n$ and $k$$(1 \leq n, k \leq 10^9)$.

For each testcase, print a single line containing a single integer, the minimum sum after performing exactly $k$ operations.

Input | Output |
---|---|

3 4 1 4 3 3 10 | 8 5 0 |

For the first case, $1, 2, 3, 4$ are written. Jesse picks $x = 3$ and replaces it by $\lfloor \frac{3}{2} \rfloor = 1$. Now the board contains $1, 2, 1, 4$ with sum $8$. For the second case, initially the board contains $1, 2, 3, 4$. For the first operation, Jesse chooses $x = 1$, replaces it by $0$. The board contains $0, 2, 3, 4$. For the second operation, Jesse chooses $x = 4$, replaces it by $2$. The board contains $0, 2, 3, 2$. For the **third**operation, Jesse chooses $x = 3$, replaces it by $1$. The board contains $0, 2, 1, 2$.
For the third case, Jesse can make everything $0$. |

Login to submit.

0%
Solution Ratio

Toph uses cookies. By continuing you agree to our Cookie Policy.