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^{th}$ ~N^{th}~ square, and wants to get to the $M^{th}$ ~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$ ~4~ things.

Go to the $(3 \times N)^{th}$ ~(3 \times N)^{th}~ square.
Go to the $(N-1)^{th}$ ~(N-1)^{th}~ square.
Go to the $(N-3)^{th}$ ~(N-3)^{th}~ square.
Go to the $\left(\dfrac{N}{2}\right)^{th}$ ~\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}$ ~M^{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 amount of moves it takes soupy boy to get to the $M^{th}$ ~M^{th}~ square, starting from the $N^{th}$ ~N^{th}~ square using the moves described above.

Sample Input 1

4 6

Sample Output 1

Sample Input 2

10 1

Sample Output 2

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.

because of the IR I could not know if my code is correct is there someways I can test my code other than the examples up there

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.

why is the memory limit so low

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!