← 返回题目列表

Codeforces · 1271/E

E. 常用号码

中文机器翻译题面 查看原题

首先,我们定义函数 $$$f(x)$$$ 如下: $$$$$$ \begin{matrix} f(x) & = & \left\{ \begin{matrix} \frac{x}{2} & \mbox{if } x \text{ is Even} \\ x - 1 & \mbox{otherwise } \end{matrix} \right。 \end{矩阵} $$$$$$

我们可以看到,如果我们选择某个值 $$$v$$$ 并将函数 $$$f$$$ 应用于它,然后将 $$$f$$$ 应用于 $$$f(v)$$$,依此类推,我们最终会得到 $$$1$$$。让我们在一个列表中写下在此过程中获得的所有值,并将该列表表示为 $$$path(v)$$$。例如,$$$path(1) = [1]$$$、$$$path(15) = [15, 14, 7, 6, 3, 2, 1]$$$、$$$path(32) = [32, 16, 8, 4, 2, 1]$$$。

让我们为从 $$$1$$$ 到 $$$n$$$ 的每个 $$$x$$$ 编写所有列表 $$$path(x)$$$。接下来的问题是:使 $$$y$$$ 包含在至少 $$$k$$$ 不同列表 $$$path(x)$$$ 中的最大值 $$$y$$$ 是多少?

正式来说,您需要找到最大值 $$$y$$$ 使得 $$$\left| \{ x ~|~ 1 \le x \le n, y \in 路径(x) \} \right| \ge k$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 10^{18}$$$)。

输出

打印唯一的整数 — 至少 $$$k$$$ 路径中包含的最大值。

示例

输入 #1

11 3

输出 #1

5

输入 #2

11 6

输出 #2

4

输入 #3

20 20

输出 #3

1

输入#4

14 5

输出#4

6

输入 #5

1000000 100

输出 #5

31248

注意

在第一个示例中,答案是 $$$5$$$,因为 $$$5$$$ 出现在 $$$path(5)$$$、$$$path(10)$$$ 和 $$$path(11)$$$ 中。

在第二个示例中,答案是 $$$4$$$,因为 $$$4$$$ 出现在 $$$path(4)$$$、$$$path(5)$$$、$$$path(8)$$$、$$$path(9)$$$、$$$path(10)$$$ 和 $$$path(11)$$$ 中。

在第三个示例中 $$$n = k$$$,因此答案是 $$$1$$$,因为 $$$1$$$ 是从 $$$1$$$ 到 $$$20$$$ 的整数的所有路径中出现的唯一数字。