← 返回题目列表

Codeforces · 743/B

B. 克洛伊和序列

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

Chloe 和 Vladik 一样,都是一位有竞争力的程序员。她没有像弗拉迪克那样去参加奥赛,但她对奥赛上提出的任务感到困惑。

让我们考虑以下生成整数序列的算法。最初,我们有一个由等于 1 的单个元素组成的序列。然后我们执行 (n - 1) 个步骤。在每一步中,我们都采用上一步中获得的序列,将其附加到其自身的末尾,并在中间插入我们之前未使用过的最小正整数。例如,第一步后得到序列[1,2,1],第二步后得到序列[1,2,1,3,1,2,1]。

任务是在获得的序列i中查找索引为k(元素从1开始编号)的元素的值。 e. (n - 1) 步骤后。

请帮助Chloe解决问题!

输入

唯一一行包含两个整数 n 和 k (1 ≤ n ≤ 50, 1 ≤ k ≤ 2n - 1)。

输出

打印单个整数 — 获得的序列中第 k 个位置的整数。

示例

输入 #1

3 2

输出 #1

2

输入 #2

4 8

输出 #2

4

注意

在第一个样本中,获得的序列为 [1, 2, 1, 3, 1, 2, 1]。第二个位置上的数字是2。

在第二个样本中,获得的序列为 [1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1]。第八个位置上的数字是4。