F 数字游戏

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

F 数字游戏

时间限制:1s

空间限制:64MB

题目背景

你可能听说过\(3N+1\)猜想,或"冰雹猜想",这是一个有趣的数字游戏。
写出一个正整数\(N\),若是奇数便变为\(3N+1\),偶数则变为\(N/2\),经过不断变换后,总会得到数字1。
(不过,正确性目前并没有得到证明。)
现在,让我们来玩一个类似的游戏。

题目描述

对于正整数\(x\),定义函数\[f(x)=\begin{cases}\frac{x}{2}, & 若x是偶数\\ x+1, & 若x是奇数 \end{cases}\]现在写出一个正整数\(x\),对其迭代\(f(x),f(f(x))....\),可以证明,最终一定会到达1。
我们将此过程中出现的所有正整数记录为列表,称为\(x\)在数字游戏中的路径\(Path[x]\)

  • 注意,一个数迭代到1后就不再进行\(f(x)\)的迭代,所以不会出现1,2,1,2,...的循环

例如
\[Path[1]=[1],Path[3]=[3,4,2,1],Path[13]=[13,14,7,8,4,2,1]\]现在我们写出\(Path[1],Path[2]...Path[n]\),问题是:求一个正整数,它在\(Path[1..n]\)的其中 至少\(k\)个 路径列表中出现。
由于有很多数满足要求,请输出最大的那一个。

输入格式

两个正整数\(n,k\),含义如上所示。

输出格式

请输出最大的至少出现\(k\)次的数。

样例输入1

10 3

样例输出1

6

样例1解释

\(6\)在\(Path[5],Path[6],Path[9],Path[10]\) 中均有出现,可以证明这是最大的满足要求的数。

样例输入2

13 1

样例输出2

14

样例2解释

\(14\)在\(Path[13]\)中出现了一次,可以证明这是最大的满足要求的数。

样例输入3

17 17

样例输出3

1

样例输入4

21968524033392639 4194303

样例输出4

10475408570

样例输入5

772324690824608498 28027536140678

样例输出5

87802

数据范围及限制

\(1\le k\le n\le 2^{63}\)

南京师范大学2021年6月程序设计竞赛(小兰赛)

未参加
状态
已结束
规则
ACM/ICPC
题目
6
开始于
2021-06-02 13:30
结束于
2021-06-02 17:30
持续时间
4.0 小时
主持人
参赛人数
199