Overview

Since the number of cells exactly doubles with each operation, we determine whether we can reach \(T\) from \(S\) by checking “whether there exists an integer \(n\) satisfying \(T = S \times 2^n\)”, and if so, find the minimum such \(n\).

Analysis

After performing the “mitosis promotion” operation \(n\) times, the number of cells always follows: $\(S \to 2S \to 4S \to \cdots \to S \times 2^n\)\( In other words, the reachable values are **only those obtained by multiplying \)S\( by \)2^n$**.

Therefore, the conditions for reaching the target \(T\) are the following two:

1. \(T\) must be a multiple of \(S\) (i.e., we can write \(T = S \times q\))
2. The ratio \(q = \dfrac{T}{S}\) must be a power of 2 (\(2^n\))

For example, when \(S=3, T=24\), we have \(q=8=2^3\), so it is reachable in 3 operations. On the other hand, if \(S=3, T=12\), then \(q=4=2^2\), so 2 operations. If \(S=3, T=18\), then \(q=6\) is not a power of 2, so it is impossible.

One could naively “keep doubling \(S\) and check if it becomes \(T\)”, but since the condition is mathematically clear, we can reliably determine it using division and “power of 2 check”. Furthermore, since \(S,T\) can be as large as \(10^{18}\), it is safer to judge simply and avoid unnecessary loops or computation.

Finally, even if it is possible, the number of operations is limited to at most \(K\), so the minimum number of operations \(n\) must satisfy \(n \le K\).

Algorithm

1. If \(T \bmod S \ne 0\), then \(T\) is not a multiple of \(S\), so output -1.
2. Compute \(q = T / S\).
3. Check whether \(q\) is a power of 2. Powers of 2 (\(1,2,4,8,\dots\)) have the form 1000...0 in binary, so: $\(q\ \&\ (q-1) = 0\)\( holds (provided \)q>0$). If this does not hold, output -1.
4. When \(q = 2^n\), the minimum number of operations is \(n = \log_2 q\). This can be computed using bit_length(): $\(n = \text{bit\_length}(q) - 1\)$
5. If \(n \le K\), output \(n\); otherwise, output -1.

Complexity

• Time complexity: \(O(1)\)
• Space complexity: \(O(1)\)

Implementation Notes

• First check \(T \% S\), and immediately return -1 if it is not divisible (avoiding unnecessary checks).

• The power of 2 check using q & (q-1) is both fast and reliable (also verify \(q>0\) to ensure \(q=0\) does not occur).

• The number of operations \(n\) can be obtained as q.bit_length() - 1 (when \(q=1\), \(n=0\), correctly handling the case where no operations are needed).

  Source Code

import sys

def main():
    S, T, K = map(int, sys.stdin.readline().split())

    if T % S != 0:
        print(-1)
        return

    q = T // S  # must be 2^n
    if q <= 0 or (q & (q - 1)) != 0:
        print(-1)
        return

    n = q.bit_length() - 1
    print(n if n <= K else -1)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.