#P3855. Minimum Operations to Reach Target
Minimum Operations to Reach Target
Minimum Operations to Reach Target
Given two positive integers S and T, your task is to determine the minimum number of operations required to convert S into T using the following operations:
- Operation 1: Multiply the current number by 2. (i.e., x becomes 2x.)
- Operation 2: Subtract 1 from the current number (this operation can only be performed if the current number is greater than 1 to ensure the result stays positive).
If it is impossible to convert S into T using the allowed operations, output no
.
Note: In this problem, it can be shown that for the given constraints, a solution exists for all valid inputs. However, you must output no
if no valid sequence of operations exists.
Constraints: 1 ≤ S, T ≤ 104.
Hint: Consider using a breadth-first search (BFS) to explore the state space.
inputFormat
The input consists of a single line containing two space-separated integers S and T.
For example:
4 7
outputFormat
Output a single integer representing the minimum number of operations required to convert S into T. If it is impossible, output no
.
For example:
2
sample
4 7
2