概要

初期個数 \(S\) の細胞を \(1\) 回ごとに \(2\) 倍に増やす「分裂促進」操作を行い、ちょうど \(T\) 個にするために必要な最小の操作回数を求める問題です。ただし、操作回数は最大 \(K\) 回までという制限があります。

考察

この問題のポイントは、細胞が「常に \(2\) 倍ずつ増える」という性質に注目することです。

1. 倍率の確認 操作を \(n\) 回行うと、細胞の数は \(S \times 2^n\) 個になります。 したがって、目標の \(T\) 個にするためには、まず \(T\) が \(S\) で割り切れること が必須条件です。もし T % S != 0 であれば、どのような操作を行ってもちょうど \(T\) 個にすることはできないため、即座に -1 と判定できます。

2. 2の累乗の判定 \(T\) が \(S\) で割り切れる場合、その倍率 \(ratio = T / S\) が \(2\) の累乗（\(2^0, 2^1, 2^2, \dots\)） になっている必要があります。 例えば：

   • \(S=3, T=12\) のとき、倍率は \(4\) です。\(4 = 2^2\) なので、操作 \(2\) 回で到達可能です。
   • \(S=3, T=9\) のとき、倍率は \(3\) です。\(3\) は \(2\) の累乗ではないため、到達不可能です。

3. 操作回数の制約 倍率が \(2^n\) と表せるとき、必要な操作回数は \(n\) 回です。この \(n\) が問題で与えられた制限 \(K\) 以内（\(n \leq K\)）であれば \(n\) を出力し、そうでなければ到達不能として -1 を出力します。

アルゴリズム

1. \(T\) が \(S\) で割り切れるかチェックします。
2. 割り切れる場合、倍率 \(ratio = T // S\) を計算します。
3. \(ratio\) が \(2\) の累乗であるかを確認します。
   • ビット演算の性質を利用すると、ratio > 0 かつ (ratio & (ratio - 1)) == 0 であれば \(2\) の累乗です。
   • あるいは、ratio を \(2\) で割り続けて確認することも可能です。
4. \(ratio = 2^n\) となる \(n\) を求めます。
   • Pythonでは ratio.bit_length() - 1 を使うことで、その数値が \(2\) の何乗であるかを効率的に取得できます。
5. \(n \leq K\) かどうかを判定し、結果を出力します。

計算量

• 時間計算量: \(O(1)\) もしくは \(O(\log(T/S))\)
  • 数値のビット長に基づいた計算やビット演算は非常に高速です。\(T, S \leq 10^{18}\) ですが、高々 \(60\) 回程度のループやビット演算で完了します。
• 空間計算量: \(O(1)\)
  • 入力値以外に保持するデータは定数個です。

実装のポイント

• 大きな数の扱い: \(S, T\) は最大 \(10^{18}\) と非常に大きいため、言語によっては 64ビット整数型（C++の long long など）を使用する必要があります。Pythonでは標準で大きな整数を扱えるため、そのまま計算可能です。

• ビット演算の活用: ratio & (ratio - 1) は、コンピュータ科学において「ある数が \(2\) の累乗かどうか」を判定する際によく使われるテクニックです。

• 特殊なケース: \(S = T\) のとき、倍率は \(1\) (\(2^0\)) となり、必要な操作回数は \(0\) 回です。このケースも上記のアルゴリズムで正しく処理できます。

  ソースコード

import sys

def solve():
    # 入力を読み込む
    line = sys.stdin.readline()
    if not line:
        return
    
    try:
        s, t, k = map(int, line.split())
    except ValueError:
        return

    # TがSで割り切れない場合は、2倍し続けてTにすることは不可能
    if t % s != 0:
        print("-1")
        return

    # 倍率を計算
    ratio = t // s
    
    # 倍率が2の累乗であるかを確認する
    # ratio & (ratio - 1) == 0 かつ ratio > 0 であれば2の累乗
    if ratio > 0 and (ratio & (ratio - 1)) == 0:
        # 2の何乗であるかを求める
        # bit_length() は 2^n のとき n + 1 を返す
        n = ratio.bit_length() - 1
        
        # 操作回数がK回以内であればその回数を出力
        if n <= k:
            print(n)
        else:
            print("-1")
    else:
        # 2の累乗でない場合は不可能
        print("-1")

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。