Board Games

Points: 7

Time limit: 1.0s

Memory limit: 256M

Author:

Problem types

Soupy boy is playing a game! He is currently on the $N^\text{th}$ ~N^\text{th}~ square, and wants to get to the $M^\text{th}$ ~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$ ~4~ things.

Go to the $(3 \times N)^\text{th}$ ~(3 \times N)^\text{th}~ square.
Go to the $(N-1)^\text{th}$ ~(N-1)^\text{th}~ square.
Go to the $(N-3)^\text{th}$ ~(N-3)^\text{th}~ square.
Go to the $\left(\dfrac{N}{2}\right)^\text{th}$ ~\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}$ ~M^\text{th}~ square?

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

Input Specification

The first and only line of input contains the two integers $N$ ~N~ and $M$ ~M~ $(1 \le N, M \le 10^5)$ ~(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}$ ~M^\text{th}~ square, starting from the $N^\text{th}$ ~N^\text{th}~ square using the moves described above.

Sample Input 1

4 6

Sample Output 1

Sample Input 2

10 1

Sample Output 2

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.

-12

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

why is the memory limit so low

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

7

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

256 megabytes is low??!?!?