Soupy boy is playing a game! He is currently on the square, and wants to get to the
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 things.
- Go to the
square.
- Go to the
square.
- Go to the
square.
- Go to the
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 square?
Note: You can assume that soupy boy will not go to a square that is larger than .
Input Specification
The first and only line of input contains the two integers and
, separated by a space.
Output Specification
Output the minimum number of moves it takes soupy boy to get to the square, starting from the
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
I am wondering how to solve this question by JAVA. It always TLE...
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
, emptyalready[]
array (allfalse
).The program will:
Set
already[7]
totrue
;Calculate
7 - 3
and add4
to the queue, sincealready[6]
is false.Calculate
7 - 1
and add6
to the queue, sincealready[4]
is false.Calculate
7 * 3
and add21
.Poll the queue: Returns
4
from the head of the queue. Setalready[4]
totrue
1
,3
,8
, and2
will be added to the queue.Poll queue: Returns
6
Set
already[6]
Calculate
6 - 3
. Add 3 to queue, sincealready[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.This comment is hidden due to too much negative feedback. Show it anyway.
256 megabytes is low??!?!?