/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は生物学の研究室で細胞培養の実験を行っています。
実験開始時点で、培養皿には S 個の細胞があります。この細胞は特殊な性質を持っており、高橋君が 1 回の「分裂促進」操作を行うと、すべての細胞が同時に分裂し、細胞の数がちょうど 2 倍になります。
高橋君が細胞の数を変化させる手段はこの「分裂促進」操作のみであり、培養皿の栄養分の都合上、この操作は 0 回以上 K 回以下しか行うことができません。
高橋君は、実験の目標として細胞の数をちょうど T 個にしたいと考えています。
細胞の数を初めの S 個からちょうど T 個にすることが可能かどうかを判定してください。可能な場合は、必要な「分裂促進」操作の最小回数を求めてください。
制約
- 1 \leq S \leq 10^{18}
- 1 \leq T \leq 10^{18}
- 0 \leq K \leq 100
- 入力はすべて整数
入力
S T K
細胞の初期個数を表す S 、目標個数を表す T 、操作可能な最大回数を表す K が、スペース区切りで 1 行に与えられる。
出力
細胞の数をちょうど T 個にすることが可能な場合は、必要な「分裂促進」操作の最小回数を 1 行で出力してください。不可能な場合は -1 を出力してください。
入力例 1
3 24 5
出力例 1
3
入力例 2
7 100 10
出力例 2
-1
入力例 3
1000000000000 8000000000000 3
出力例 3
3
Score : 300 pts
Problem Statement
Takahashi is conducting a cell cultivation experiment in a biology laboratory.
At the start of the experiment, there are S cells in the culture dish. These cells have a special property: when Takahashi performs one "mitosis promotion" operation, all cells divide simultaneously, and the number of cells exactly doubles.
The only means Takahashi has to change the number of cells is this "mitosis promotion" operation, and due to the nutrient limitations of the culture dish, this operation can only be performed between 0 and K times, inclusive.
Takahashi's experimental goal is to make the number of cells exactly T.
Determine whether it is possible to change the number of cells from the initial S to exactly T. If it is possible, find the minimum number of "mitosis promotion" operations required.
Constraints
- 1 \leq S \leq 10^{18}
- 1 \leq T \leq 10^{18}
- 0 \leq K \leq 100
- All inputs are integers
Input
S T K
S representing the initial number of cells, T representing the target number of cells, and K representing the maximum number of operations allowed are given on a single line separated by spaces.
Output
If it is possible to make the number of cells exactly T, output the minimum number of "mitosis promotion" operations required on a single line. If it is impossible, output -1.
Sample Input 1
3 24 5
Sample Output 1
3
Sample Input 2
7 100 10
Sample Output 2
-1
Sample Input 3
1000000000000 8000000000000 3
Sample Output 3
3