← 返回题目列表

AtCoder · kupc2017_b

B. 樟树

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

分数: 100 点

问题陈述

京都大学钟楼前有一棵巨大的楠树。据报道,该楠木具有以下结构。

  • 存在一个正整数 N 楠木有 2^N-1 分支点,编号从 1 to 2^N-1.
  • 对于每个整数 i 持有 1 \leq i \leq 2^{N-1}-1,楠木根据以下规则设有分支机构。
    • 分支点 i 和 2i 与分支相连。
    • 分支点 i 和 2i + 1 与分支相连。
  • 没有任何分支不遵守上述规则。

例如,对于 N=3,kusunoki的结构如下。

楠木 N=3

你想爬这座楠木。 可以从分支点爬上去 S to T 当且仅当 S=T 或存在来自以下分支的路径 S to T,其中分支点的数量按升序排列 S to T。 给定两个整数 S 和 T,判断是否可以从分支点攀爬 S to T。 另外,如果可能的话,请回答您需要攀爬的最少树枝数。

约束

  • 1 \leq N \leq 25
  • 1 \leq S \leq 2^N-1
  • 1 \leq T \leq 2^N-1
  • N,S,T 是整数。

输入

输入由标准输入按以下格式给出:

N S T

输出

如果你无法从 S to T,打印 -1。 否则,打印您需要攀爬的最少分支数。


示例输入 1

3 2 4

示例输出 1

1

因为你可以从分支点爬上去 2 to 4 通过一个分支,打印 1.


示例输入 2

3 7 1

示例输出 2

-1

示例输入 3

4 2 2

示例输出 3

0