E. Common Number
binary search; combinatorics; dp; math
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$$$.
The first line contains two integers \(n\) and \(k\) (\(1 \le k \le n \le 10^{18}\)).
Print the only integer — the maximum value that is contained in at least \(k\) paths.
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\).