Board Games

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

Soupy boy is playing a game! He is currently on the N^{th} square, and wants to get to the M^{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)^{th} square.
  • Go to the (N-1)^{th} square.
  • Go to the (N-3)^{th} square.
  • Go to the \left(\dfrac{N}{2}\right)^{th} square if the current square is even.

Can you tell soupy boy what is the minimum amount of moves so that he can get to the M^{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 amount of moves it takes soupy boy to get to the M^{th} square, starting from the N^{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


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

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


    • 2
      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.


  • -5
    MinzeLI  commented on Feb. 12, 2020, 1:08 a.m.

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 2
      kayano  commented on Feb. 12, 2020, 6:53 a.m.

      I think it's pretty easy to make your own test cases for this problem, just input two random large integers.


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

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 6
      NathanDoesDMOJ  commented on July 8, 2020, 5:21 p.m.

      256 megabytes is low??!?!?


    • -3
      aayushICS  commented on April 8, 2020, 9:13 p.m.

      That's some cheese!