Common Number

2000ms

262144K

Description:

At first, let's define function $$$f(x)$$$ as follows: $$$$$$ \begin{matrix} f(x) & = & \left\{ \begin{matrix} \frac{x}{2} & \mbox{if } x \text{ is even} \\ x - 1 & \mbox{otherwise } \end{matrix} \right. \end{matrix} $$$$$$

We can see that if we choose some value $$$v$$$ and will apply function $$$f$$$ to it, then apply $$$f$$$ to $$$f(v)$$$, and so on, we'll eventually get $$$1$$$. Let's write down all values we get in this process in a list and denote this list as $$$path(v)$$$. For example, $$$path(1) = [1]$$$, $$$path(15) = [15, 14, 7, 6, 3, 2, 1]$$$, $$$path(32) = [32, 16, 8, 4, 2, 1]$$$.

Let's write all lists $$$path(x)$$$ for every $$$x$$$ from $$$1$$$ to $$$n$$$. The question is next: what is the maximum value $$$y$$$ such that $$$y$$$ is contained in at least $$$k$$$ different lists $$$path(x)$$$?

Formally speaking, you need to find maximum $$$y$$$ such that $$$\left| \{ x ~|~ 1 \le x \le n, y \in path(x) \} \right| \ge k$$$.

Input:

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^{18}$$$).

Output:

Print the only integer — the maximum value that is contained in at least $$$k$$$ paths.

Sample Input:

11 3

Sample Output:

Sample Input:

11 6

Sample Output:

Sample Input:

20 20

Sample Output:

Sample Input:

14 5

Sample Output:

Sample Input:

1000000 100

Sample Output:

Note:

In the first example, the answer is $$$5$$$, since $$$5$$$ occurs in $$$path(5)$$$, $$$path(10)$$$ and $$$path(11)$$$.

In the second example, the answer is $$$4$$$, since $$$4$$$ occurs in $$$path(4)$$$, $$$path(5)$$$, $$$path(8)$$$, $$$path(9)$$$, $$$path(10)$$$ and $$$path(11)$$$.

In the third example $$$n = k$$$, so the answer is $$$1$$$, since $$$1$$$ is the only number occuring in all paths for integers from $$$1$$$ to $$$20$$$.

Informação

Provedor Codeforces

Código CF1271E