概要

初期値 \(S\) の細胞が、1回の操作で2倍になる性質を持つとき、最大 \(K\) 回の操作で細胞数をちょうど \(T\) にできるか判定し、可能な場合は最小操作回数を求めます。

考察

細胞は1回の操作で2倍になるので、\(x\) 回操作すると細胞数は \(S \times 2^x\) になります。
目標はこの値をちょうど \(T\) に一致させることです：

\[ S \times 2^x = T \]

この式を変形すると：

\[ 2^x = \frac{T}{S} \]

したがって、\(\frac{T}{S}\) が2のべき乗であるかどうかを判定すればよいことがわかります。
また、\(S > T\) の場合はそもそも達成できないので、その場合は -1 を出力します。

さらに、\(\frac{T}{S}\) が整数でない場合も達成できないため、事前に \(T\) が \(S\) で割り切れるか確認する必要があります。

最後に、求めたべき乗回数 \(x\) が操作上限 \(K\) を超えていないかも確認します。

素朴なアプローチでは…

例えば、1回ずつ操作をシミュレートして \(S \times 2^x\) を計算していくと、\(S\) や \(T\) が非常に大きいため、計算時間がかかりすぎます（TLE）。
また、浮動小数点演算による誤差も発生しうるため、整数ベースで処理するのが望ましいです。

解決方法

\(\frac{T}{S}\) が整数であり、かつ2のべき乗であることを効率的に判定するために、ビット演算を利用します。
ある正の整数 \(n\) が2のべき乗であることは、以下のように判定できます：

\[ n > 0 \land (n \& (n - 1)) = 0 \]

この条件を満たせば、\(n = 2^x\) となる整数 \(x\) が存在します。
そして、その \(x\) は \(\log_2(n)\) で求められます。

アルゴリズム

1. \(S > T\) なら -1 を出力（初期状態より減らせない）
2. \(S = T\) なら 0 を出力（操作不要）
3. \(T\) が \(S\) で割り切れないなら -1（到達不能）
4. \(T / S\) を計算し、それが2のべき乗かビット演算で判定
5. 2のべき乗であれば \(\log_2\) により指数 \(x\) を求め、\(x \leq K\) なら \(x\) を出力、そうでなければ -1

計算量

• 時間計算量: \(O(1)\)
• 空間計算量: \(O(1)\)

実装のポイント

• 浮動小数点演算を使わず、整数演算とビット演算で判定すること
• 割り切れない場合や負数の場合の処理を忘れずに
• Pythonの math.log2() は整数の2冪に対しては正確に整数を返すが、念のため整数型にキャストする

## ソースコード

```python
import math

def main():
    S, T, K = map(int, input().split())
    
    if S > T:
        print(-1)
        return
    
    if S == T:
        print(0)
        return
    
    # S * 2^x >= T となる最小の非負整数 x を求める
    # つまり 2^x >= T/S
    # x >= log2(T/S)
    # ただし、T/S が整数でない場合も考慮して、2^x * S >= T が必要
    # 実際に 2^x * S >= T かつ 2^x * S <= T であるかを確認する必要がある
    # しかし、S=1, T=3 のような場合、2^x = 3 となる整数xは存在しない
    
    # まず、S * 2^x = T となるような x が存在するかを確認する
    # これは T が S * 2^x の形で表せるかということ
    
    # T が S で割り切れないなら無理
    if T % S != 0:
        print(-1)
        return
    
    ratio = T // S
    
    # ratio が 2 のべき乗か？
    # 2 のべき乗 <=> ratio > 0 かつ (ratio & (ratio - 1)) == 0
    if ratio <= 0 or (ratio & (ratio - 1)) != 0:
        print(-1)
        return
    
    # ratio = 2^x となる x を求める
    x = int(math.log2(ratio))
    
    # x が K 以下なら可能
    if x <= K:
        print(x)
    else:
        print(-1)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。