分数: 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