306925: CF1271E. Common Number

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Common Number

题意翻译

定义函数 $f(x)$,$f(x)=\begin{cases} x-1&x \bmod 2 = 1\\ \frac{x}{2}&x \bmod 2 = 0 \end{cases}$ 可以发现对于任意的 $x$ ,不断令 $x=f(x)$ ,最终一定会得到 $1$ 。 定义 $path_x$ 为在这个过程中出现过的所有值的集合。 例如 $path_1=\{1\}$,$path_{15}=\{15,14,7,6,3,2,1\}$ 。 写下所有的 $path_i,1 \le i \le n,i \in N_+$ 。 求最大的 $y$ ,使得存在至少 $k$ 个互异的 $j$ ,使得 $y \in path_j$ 。

题目描述

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} $ $ </p><p>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\] $ .</p><p>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) $ ?</p><p>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.

输入输出样例

输入样例 #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

说明

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 $ .

Input

题意翻译

定义函数 $f(x)$,$f(x)=\begin{cases} x-1&x \bmod 2 = 1\\ \frac{x}{2}&x \bmod 2 = 0 \end{cases}$ 可以发现对于任意的 $x$ ,不断令 $x=f(x)$ ,最终一定会得到 $1$ 。 定义 $path_x$ 为在这个过程中出现过的所有值的集合。 例如 $path_1=\{1\}$,$path_{15}=\{15,14,7,6,3,2,1\}$ 。 写下所有的 $path_i,1 \le i \le n,i \in N_+$ 。 求最大的 $y$ ,使得存在至少 $k$ 个互异的 $j$ ,使得 $y \in path_j$ 。

加入题单

上一题 下一题 算法标签: