#P3855. Minimum Operations to Reach Target

    ID: 17103 Type: Default 1000ms 256MiB

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