Board Games

View as PDF
Submit solution
Points: 7
Time limit: 1.0s
Memory limit: 256M
Author:
magicalsoup
Problem types

Soupy boy is playing a game! He is currently on the N^\text{th} square, and wants to get to the M^\text{th} square exactly. However, moves in this game are a bit different than your average board game.

Starting from the current square, he can do one of 4 things.

  • Go to the (3 \times N)^\text{th} square.
  • Go to the (N-1)^\text{th} square.
  • Go to the (N-3)^\text{th} square.
  • Go to the \left(\dfrac{N}{2}\right)^\text{th} square if the current square is even.

Can you tell soupy boy what is the minimum number of moves so that he can get to the M^\text{th} square?

Note: You can assume that soupy boy will not go to a square that is larger than 10^7.

Input Specification

The first and only line of input contains the two integers N and M (1 \le N, M \le 10^5), separated by a space.

Output Specification

Output the minimum number of moves it takes soupy boy to get to the M^\text{th} square, starting from the N^\text{th} square using the moves described above.

Sample Input 1

4 6

Sample Output 1

2

Sample Input 2

10 1

Sample Output 2

3

Comments


  • -1
    YidiChen  commented on Sept. 6, 2020, 11:54 p.m.

    I am wondering how to solve this question by JAVA. It always TLE...


    • 7
      billsboard  commented on Dec. 16, 2020, 8:42 p.m. ← edit 2

      Your method for checking already visited squares has a problem. It is possible for the same square to be added multiple times to your queue without the already flag being set.

      Example: Currently on square 7, empty already[] array (all false).

      The program will:

      Set already[7] to true;

      Calculate 7 - 3 and add 4 to the queue, since already[6] is false.

      Calculate 7 - 1 and add 6 to the queue, since already[4] is false.

      Calculate 7 * 3 and add 21.

      Poll the queue: Returns 4 from the head of the queue. Set already[4] to true

      1, 3, 8, and 2 will be added to the queue.

      Poll queue: Returns 6

      Set already[6]

      Calculate 6 - 3. Add 3 to queue, since already[3] == false.

      Now see what happened. 3 was added twice to the queue, and will be processed twice, cells are only marked as completed when they are pulled from the queue, not when they are added.


  • -13
    MinzeLI  commented on Feb. 12, 2020, 1:02 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.