Overview

Given a cell with initial value \(S\) that doubles with each operation, determine whether the cell count can be made exactly \(T\) in at most \(K\) operations, and if possible, find the minimum number of operations.

Analysis

Since the cell doubles with each operation, after \(x\) operations the cell count becomes \(S \times 2^x\). The goal is to make this value exactly equal to \(T\):

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

Rearranging this equation:

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

Therefore, we need to determine whether \(\frac{T}{S}\) is a power of 2. Also, if \(S > T\), it is impossible to achieve, so we output -1 in that case.

Furthermore, if \(\frac{T}{S}\) is not an integer, it is also impossible to achieve, so we need to check in advance whether \(T\) is divisible by \(S\).

Finally, we also need to verify that the computed exponent \(x\) does not exceed the operation limit \(K\).

With a naive approach…

For example, if we simulate operations one at a time computing \(S \times 2^x\), since \(S\) and \(T\) can be very large, the computation takes too long (TLE). Additionally, floating-point arithmetic can introduce errors, so it is preferable to process everything using integer-based operations.

Solution

To efficiently determine whether \(\frac{T}{S}\) is an integer and a power of 2, we use bit operations. A positive integer \(n\) is a power of 2 if and only if:

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

If this condition is satisfied, there exists an integer \(x\) such that \(n = 2^x\). Then, \(x\) can be obtained as \(\log_2(n)\).

Algorithm

1. If \(S > T\), output -1 (cannot decrease from the initial state)
2. If \(S = T\), output 0 (no operation needed)
3. If \(T\) is not divisible by \(S\), output -1 (unreachable)
4. Compute \(T / S\) and check whether it is a power of 2 using bit operations
5. If it is a power of 2, compute the exponent \(x\) using \(\log_2\), and output \(x\) if \(x \leq K\), otherwise output -1

Complexity

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

Implementation Notes

• Use integer arithmetic and bit operations instead of floating-point arithmetic for the check

• Don’t forget to handle cases where division is not exact or values are negative

• Python’s math.log2() returns an exact integer for integer powers of 2, but cast to an integer type just to be safe

  Source Code

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()

This editorial was generated by qwen3-coder-480b.