/ 
Time Limit: 1 sec / Memory Limit: 256 MB
配点 100 点
問題文
京都大学の時計台の前には巨大なクスノキが生えています。 観察の結果、このクスノキの構造について次のことが分かっています。
- ある正整数 N があり、クスノキには 2^N-1 個の分岐点が存在する。
- 分岐点は 1 から 2^N-1 まで番号付けられている。
- 1 \leq i \leq 2^{N-1}-1 を満たす各整数 i について以下のように枝がある。
- 分岐点 i と分岐点 2i が枝で繋がっている。
- 分岐点 i と分岐点 2i+1 が枝で繋がっている。
- 上で述べられた条件を満たさない枝は存在しない。
例えば N=3 のときのクスノキの構造は下の図のようになっています．
クスノキ N=3
あなたは、このクスノキを登りたいと考えています。 クスノキの分岐点 S から T まで木登り可能であるとは、S=T であるか、または分岐点 S から分岐点 T まで通過する分岐点の番号が増大するように枝をたどっていくことができることを言います。 分岐点の番号 S と分岐点の番号 T が与えられるので S から 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 から T へ木登り可能でないときは -1 を出力せよ。
S から T へ木登り可能であるときは通過する必要のある枝の本数を出力せよ。
入力例1
3 2 4
出力例1
1
分岐点 2 から 4 に木登り可能であり枝を 1 本通過するので 1 を出力します。
入力例2
3 7 1
出力例2
-1
入力例3
4 2 2
出力例3
0
Score : 100 points
Problem Statement
There is a huge kusunoki (camphor tree) in front of the clock tower of Kyoto University. It is reported that this kusunoki has the following structure.
- There exists a positive integer N and the kusunoki has 2^N-1 branch points, which are numbered from 1 to 2^N-1.
- For each integer i that holds 1 \leq i \leq 2^{N-1}-1, the kusunoki has branches according to the following rules.
- Branch point i and 2i are connected with a branch.
- Branch point i and 2i + 1 are connected with a branch.
- There is no branch that does not hold the above rules.
For example, for N=3, the structure of the kusunoki is as follows.
Kusunoki N=3
You want to climb this kusunoki. You can climb from branch point S to T if and only if S=T or there exists a path of branches from S to T, where the numbers of branch points are in ascending order from S to T. Given two integers S and T, determine whether you can climb from branch point S to T. Also, if it is possible, answer the lowerst number of branches you need to climb.
Constraints
- 1 \leq N \leq 25
- 1 \leq S \leq 2^N-1
- 1 \leq T \leq 2^N-1
- N,S,T are integers.
Input
Input is given from Standard Input in the following format:
N S T
Output
If you can not climb from S to T, print -1.
Otherwise, print the lowest number of branches you need to climb.
Sample Input 1
3 2 4
Sample Output 1
1
Since you can climb from branch point 2 to 4 through one branch, print 1.
Sample Input 2
3 7 1
Sample Output 2
-1
Sample Input 3
4 2 2
Sample Output 3
0