Your car starts at position 0 and speed +1 on an infinite number line.  (Your car can go into negative positions.)
Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).
When you get an instruction "A", your car does the following: position += speed, speed *= 2.
When you get an instruction "R", your car does the following: if your speed is positive then speed = -1 , otherwise speed = 1.  (Your position stays the same.)
For example, after commands "AAR", your car goes to positions 0->1->3->3, and your speed goes to 1->2->4->-1.
Now for some target position, say the length of the shortest sequence of instructions to get there.
Example 1:
Input: 
target = 3
Output: 2
Explanation: 
The shortest instruction sequence is "AA".
Your position goes from 0->1->3.

Example 2:
Input: 
target = 6
Output: 5
Explanation: 
The shortest instruction sequence is "AAARA".
Your position goes from 0->1->3->7->7->6.

 
Note: 

1 <= target <= 10000.

Difficulty: interview

Starter code:

class Solution:
    def racecar(self, target: int) -> int:
        

Solutions:
class Solution:
    dp = {0: 0}
    def racecar(self, target: int) -> int:
        if target in self.dp:
            return self.dp[target]
        n = target.bit_length()
        if 2**n - 1 == target:
            self.dp[target] = n
        else:
            self.dp[target] = self.racecar(2**n - 1 - target) + n + 1
            for m in range(n - 1):
                self.dp[target] = min(self.dp[target], self.racecar(target - 2**(n - 1) + 2**m) + n + m + 1)
        return self.dp[target]

class Solution:
    def racecar(self, target: int) -> int:
        dist = [float('inf')] * (target + 1)
        dist[0] = 0 # the minimum number of steps to achieve i with starting speed being 1
        #dist[1] = 1
        #dist[2] = 4
        #dist[3] = 2
        
        for t in range(1, target+1):
            k = t.bit_length()
            up_limit = 2**k-1
            if t == up_limit: # right on the target by only move forward with no reverse
                dist[t] = k
            
            # between two critical points (k-1 steps and k steps)
            # the last move is forward move
            # in this case there should be even number of turns, which results in odd number of consecutive acceleration period. To recurse into the original problem (starting speed is 1 and point to the target) we need to remove the first two turns (or last two turns) 
            for j in range(1, k):
                for q in range(j):
                    dist[t] = min(dist[t], dist[t-2**j + 2**q]+j+1+q+1) # the last move is forward
            
            dist[t] = min(dist[t], dist[2**k-1-t]+k+1) # the last move is backward
            
            
            
        return dist[target]
            
        
        
        


class Solution:
    def racecar(self, target: int) -> int:
        q = deque([(0, 1, 0)])
        encountered = set()
        while q:
            pos, spd, length = q.popleft()
            if (pos, spd) in encountered: continue
            else: encountered.add((pos, spd))
            if pos == target: 
                return length
            if (pos + spd, spd * 2) not in encountered:
                if abs(pos + spd) <= 2 * target + 1:
                    q.append((pos + spd, spd * 2, length + 1))
            revSpd = -1 if spd > 0 else 1
            if (pos, revSpd) not in encountered:
                q.append((pos, revSpd, length + 1))
        return -1

from collections import deque
class Solution:
    def racecar(self, target: int) -> int:
        
        steps = 0
        queue = deque([(0, 1)])
        cache = {(0,1)}
        while queue:
            for _ in range(len(queue)):
                p, s = queue.popleft()
                if p == target:
                    return steps
                p1,s1 = p+s, s*2
                p2 = p
                s2 = -1 if s > 0 else 1
                
                if -20000 <= p1 <= 20000 and (p1,s1) not in cache:
                    cache.add((p1,s1))
                    queue.append((p1,s1))
                if -20000 <= p2 <= 20000 and  (p2,s2) not in cache:
                    cache.add((p2,s2))
                    queue.append((p2,s2))
            steps += 1

                
            
            


class Solution:
    def racecar(self, target: int) -> int:
        nodes = [(0, 1)]
        seen, length = set([(0, 1), (0, -1)]), 0
        while nodes:
            new_nodes = []
            for pos, speed in nodes:
                if pos == target:
                    return length
                # A
                for new_pos, new_speed in [
                    (pos + speed, speed * 2),
                    (pos, -1 if speed > 0 else 1),
                ]:
                    if abs(new_speed) > 2 * target or abs(new_pos) > 2 * target:
                        continue
                    if (new_pos, new_speed) not in seen:
                        seen.add((new_pos, new_speed))
                        new_nodes.append((new_pos, new_speed))
            length += 1
            nodes = new_nodes
        return -1

class Solution:
    def racecar(self, target: int) -> int:
        q = deque([(0, 1, 0)])
        encountered = set()
        while q:
            pos, spd, length = q.popleft()
            if (pos, spd) in encountered: continue
            else: encountered.add((pos, spd))
            if pos == target: 
                return length
            if (pos + spd, spd * 2) not in encountered:
                if abs(pos + spd) <= 2 * target + 1 and abs(spd) <= 2 * target:
                    q.append((pos + spd, spd * 2, length + 1))
            revSpd = -1 if spd > 0 else 1
            if (pos, revSpd) not in encountered:
                q.append((pos, revSpd, length + 1))
        return -1

class Solution1:
    
    def __init__(self):
        self.dp = {0: 0}
    
    def racecar(self, target: int) -> int:
        if target in self.dp:
            return self.dp[target]
        n = target.bit_length()
        if 2 ** n - 1 == target:
            self.dp[target] = n
        else:
            self.dp[target] = self.racecar(2 ** n - 1 - target) + n + 1
            for m in range(n - 1):
                self.dp[target] = min(self.dp[target], 
                                 self.racecar(target - 2 ** (n - 1) + 2 ** m) + n + m + 1)
                
        return self.dp[target]
            
        
class Solution2:
    def racecar(self, target: int) -> int:
    # #analysis + DP
        memo = [-1] * (target * 2)
        def DP(s):
            if memo[s] > 0: return memo[s]
            duishu = math.log2(s+1)
            if int(duishu) == duishu: 
                memo[s] = duishu
                return duishu
            left = int(duishu)
            right = int(duishu) + 1
            memo[s] = right + 1 + DP(2**right - s - 1)
            for i in range(left):
                huizou = 2**i - 1
                memo[s] = min(memo[s], left + i + 2 + DP(s - 2**left + 1 + huizou))
            return memo[s]
        return int(DP(target))
        
    
    
    
    
class Solution:
    def racecar(self, target: int) -> int:    
    #classic BFS
        visited = {(0,1)}
        queue = collections.deque()
        queue.append((0,1))
        steps = 0
        while queue:
            size = len(queue)
            for _ in range(size):
                s, v = queue.popleft()
                if s == target: return steps
                # 'A'
                cur_s = s + v
                cur_v = v * 2
                if (cur_s, cur_v) not in visited and s >= 0:
                    queue.append((cur_s, cur_v))
                    visited.add((cur_s, cur_v))
                #'R'
                cur_s = s
                cur_v = -1 if v > 0 else 1
                if (cur_s, cur_v) not in visited and s >= 0:
                    queue.append((cur_s, cur_v))
                    visited.add((cur_s, cur_v))
            steps += 1

class Solution:
    def racecar(self, target):
        q, cnt, used = [(0, 1)], 0, {(0, 1)}
        while q:
            new = []
            for pos, speed in q:
                if pos == target:
                    return cnt
                elif pos > 20000 or -20000 > pos:
                    continue
                if (pos + speed, speed * 2) not in used:
                    new.append((pos + speed, speed * 2))
                    used.add((pos + speed, speed * 2))
                if speed > 0 and (pos, -1) not in used:
                    new.append((pos, -1))
                    used.add((pos, -1))
                elif speed < 0 and (pos, 1) not in used:
                    new.append((pos, 1))
                    used.add((pos, 1))
            q = new
            cnt += 1

class Solution:
    def racecar(self, target: int) -> int:
        visited = {(0,1)}
        queue = collections.deque()
        queue.append((0,1))
        steps = 0
        while queue:
            size = len(queue)
            for _ in range(size):
                s, v = queue.popleft()
                if s == target: return steps
                # 'A'
                cur_s = s + v
                cur_v = v * 2
                if (cur_s, cur_v) not in visited and s >= 0:
                    queue.append((cur_s, cur_v))
                    visited.add((cur_s, cur_v))
                #'R'
                cur_s = s
                cur_v = -1 if v > 0 else 1
                if (cur_s, cur_v) not in visited and s >= 0:
                    queue.append((cur_s, cur_v))
                    visited.add((cur_s, cur_v))
            steps += 1

class Solution:
    def racecar(self, target: int) -> int:
        
        q = [(0,1)]
        vis = set([(0,1)])
        ans=0
        while q:
            new_q = []
            for p,s in q:
                if p==target:
                    return ans
                p1,s1 = p+s,2*s
                p2,s2 = p, -1 if s>0 else 1
                # if (p1,s1) not in vis:
                #     vis.add((p1,s1))
                new_q.append((p1,s1))
                if (p2,s2) not in vis:
                    vis.add((p2,s2))
                    new_q.append((p2,s2))
            q = new_q
            ans+=1
        return -1


class Solution:
    def racecar(self, target):
        K = target.bit_length() + 1
        barrier = 2**K
        pq = [(0, target)]
        dist = [float('inf')] * (2 * barrier + 1)
        dist[target] = 0

        while pq:
            steps, targ = heapq.heappop(pq)
            if dist[targ] > steps: continue

            for k in range(K+1):
                walk = (2**k) - 1
                steps2, targ2 = steps + k + 1, walk - targ
                if walk == targ: steps2 -= 1 #No \"R\" command if already exact

                if abs(targ2) <= barrier and steps2 < dist[targ2]:
                    heapq.heappush(pq, (steps2, targ2))
                    dist[targ2] = steps2

        return dist[0]

class Solution:
    def racecar(self, target: int) -> int:
        
        q = [(0,1)]
        vis = {(0,1)}
        ans=0
        while q:
            new_q = []
            for p,s in q:
                if p==target:
                    return ans
                p1,s1 = p+s,2*s
                p2,s2 = p, -1 if s>0 else 1
                # if (p1,s1) not in vis:
                #     vis.add((p1,s1))
                new_q.append((p1,s1))
                if (p2,s2) not in vis:
                    vis.add((p2,s2))
                    new_q.append((p2,s2))
            q = new_q
            ans+=1
        return -1


class Solution:
    def racecar(self, target: int) -> int:
        queue = deque([(0, 1, 0)])
        seen = {(0, 1)}
        while queue:
            pos, speed, cost = queue.popleft()
            if pos == target:
                return cost
            
            # A
            new_pos, new_speed = pos + speed, speed * 2
            if new_pos > 0 and (new_pos, new_speed) not in seen:
                seen.add((new_pos, new_speed))
                queue.append((new_pos, new_speed, cost + 1)) # A
                
            # R
            reverse_speed = -1 if speed > 0 else 1
            if (pos, reverse_speed) not in seen:
                seen.add((pos, reverse_speed))
                queue.append((pos, reverse_speed, cost + 1))


class Solution:
    def racecar1(self, target: int) -> int:
        # bfs 能够快速想起来的方法！剪枝的策略不理解！
        q = collections.deque()
        q.append([0, 1])
        visited = set()
        visited.add('0_1')
        visited.add('0_-1')
        steps = 0
        while q:
            qsize = len(q)
            for i in range(qsize):
                pos, speed = q.popleft()
                
                pos1 = pos + speed
                speed1 = speed * 2 # 加速！注意第一个可能性的构造方法：首先是新的pos1，然后是新的速度！
                if pos1 == target:
                    return steps + 1
                p1 = [pos1, speed1]
                #key1 = '{}_{}'.format(pos1, speed1)
                if abs(speed1) < 2*target and abs(pos1) < 2*target and not key1 in visited: #相当于说，如果>= 2*target的时候，就剪枝了！
                    q.append(p1) #如果 < ??? # 这里没有把p1加入visited???
                    #visited.add(key1) # this makes things slower... yet still can pass!
                
                speed2 = -1 if speed > 0 else 1 # 掉头！注意是维持pos位置不变，速度如果原来是》0，则变成-1，如果是《0则变成1！！
                p2 = [pos, speed2]
                key2 = '{}_{}'.format(pos, speed2)
                if key2 not in visited:
                    q.append(p2)
                    visited.add(key2)
            steps += 1
        return -1
    
    def racecar(self, target):
        k = target.bit_length() + 1
        barrier = 1<<k
        pq = [(0, target)]
        dist = [float('inf')] * (2 * barrier + 1)
        dist[target] = 0
        
        while pq:
            steps, targ = heapq.heappop(pq)
            if dist[targ] > steps: continue
            
            for k2 in range(k+1):
                walk = (1<<k2) - 1
                steps2, targ2 = steps + k2 + 1, walk - targ
                if walk == targ:
                    steps2 -= 1
                
                if abs(targ2) <= barrier and steps2 < dist[targ2]:
                    heapq.heappush(pq, (steps2, targ2))
                    dist[targ2] = steps2
        return dist[0]

class Solution:
    def racecar(self, target: int) -> int:
        queue = collections.deque([(1, 0)])
        visited = set(queue)
        count = 0
        while queue:
            for _ in range(len(queue)):
                speed, pos = queue.popleft()
                if pos < -sqrt(target):
                    continue
                
                if target == pos:
                    return count
                
                if (speed*2, pos+speed) not in visited:
                    visited.add((speed*2, pos+speed))
                    queue.append((speed*2, pos+speed))
                
                if speed > 0:
                    if (-1, pos) not in visited:
                        visited.add((-1, pos))
                        queue.append((-1, pos))
                else:
                    if (1, pos) not in visited:
                        visited.add((1, pos))
                        queue.append((1, pos))
            count += 1
        return -1

class Solution:
    def racecar(self, target: int) -> int:
        layer = collections.deque([(0,1)])
        visited = set()
        ans = 0
        while len(layer) > 0:
            nxt_layer = collections.deque()
            while len(layer) > 0:
                p, s = layer.popleft()
                if p > target*2 and s > target*2:
                    continue
                if p == target:
                    return ans
                nxt_a = (p+s, 2*s)
                if nxt_a not in visited:
                    nxt_layer.append(nxt_a)
                    visited.add(nxt_a)
                nxt_r = (p, -1 if s > 0 else 1)
                if nxt_r not in visited:
                    nxt_layer.append(nxt_r)
                    visited.add(nxt_r)
            layer= nxt_layer
            ans+=1

class Solution:
    def racecar(self, target: int) -> int:
        if target == 0:
            return 0
        
        pq = [(0, 0, -1)] # steps, pos, speed
        visited = set([(0, -1)])
        
        while pq:
            steps, pos, speed = heapq.heappop(pq)
            
            next_steps, next_pos, next_speed = steps + 1, pos + speed, speed * 2
            
            if -next_pos == target:
                return next_steps
            
            if -2 * target < -next_pos < 2 * target and -2 * target < -next_speed < 2 * target and not (next_pos, next_speed) in visited:
            # if -next_pos < 2 * target and -next_speed < 2 * target and not (next_pos, next_speed) in visited:
                heapq.heappush(pq, (next_steps, next_pos, next_speed))
                visited.add((next_pos, next_speed))
            
            if speed > 0 and not (pos, -1) in visited:
                heapq.heappush(pq, (next_steps, pos, -1))
                visited.add((pos, -1))
            elif speed < 0 and not (pos, 1) in visited:
                heapq.heappush(pq, (next_steps, pos, 1))
                visited.add((pos, 1))
        return -1

class Solution:
    def racecar(self, target: int) -> int:
        queue = collections.deque([(1, 0)])
        visited = set(queue)
        count = 0
        while queue:
            for _ in range(len(queue)):
                speed, pos = queue.popleft()
                if pos < -(target/2):
                    continue
                
                if target == pos:
                    return count
                
                if (speed*2, pos+speed) not in visited:
                    visited.add((speed*2, pos+speed))
                    queue.append((speed*2, pos+speed))
                
                if speed > 0:
                    if (-1, pos) not in visited:
                        visited.add((-1, pos))
                        queue.append((-1, pos))
                else:
                    if (1, pos) not in visited:
                        visited.add((1, pos))
                        queue.append((1, pos))
            count += 1
        return -1

class Solution:
    def racecar(self, target: int) -> int:
        if target == 0:
            return 1
        self.ans = 0
        self.bfsHelper(target)
        return self.ans
        
        
    def bfsHelper(self, target):
        queue = []
        queue.append((0, 1))
        visited = set()
        key = 'pos_' + str(0) + 'speed_' + str(1)
        visited.add(key)
        
        while len(queue) > 0:
            size = len(queue)
            for i in range(size):
                curPos = queue[0][0]
                curSpeed = queue[0][1]
                queue.pop(0)
                if curPos == target:
                    return self.ans
                
                newPos = curPos + curSpeed
                newSpeed = curSpeed * 2
                key = 'pos_' + str(newPos) + 'speed_' + str(newSpeed)
                if key not in visited and newPos > 0 and newPos < 2 * target:
                    visited.add(key)
                    queue.append((newPos, newSpeed))

                newPos = curPos
                newSpeed = -1 if curSpeed > 0 else 1
                key = 'pos_' + str(newPos) + 'speed_' + str(newSpeed)
                if key not in visited and newPos > 0 and newPos < 2 * target:
                    visited.add(key)
                    queue.append((newPos, newSpeed))
            
            self.ans += 1
            
        self.ans = -1

        
        


import bisect

class Solution:
    def racecar(self, target: int) -> int:
        speed = 1
        dis = [0]
        while dis[-1] < target:
            dis.append(dis[-1] + speed)
            speed *= 2
        
        num_moves  = self.recur(target, dis, {})
        return num_moves
        
        
    def recur(self, target: int, dis: list, memo: dict) -> int:
        if target in memo:
            return memo[target]
        
        if target in dis:
            return dis.index(target)
        
        index = bisect.bisect_left(dis, target) - 1
        
        moves_right = self.recur(dis[index + 1] - target, dis, memo) + 2 + index
        moves_left = self.recur(target - dis[index], dis, memo) + 2 + index
        
        for i in range(1, index):
            new_moves_left = index + 1 + i + 1 + self.recur(target - dis[index] + dis[i], dis, memo)
            moves_left = min(moves_left, new_moves_left)

        
        memo[target] = min(moves_right, moves_left)

        return min(moves_right, moves_left)
            
        

        
        


class Solution:
    def racecar(self, target: int) -> int:
        q = deque([(0, 1, 0)])
        encountered = set()
        while q:
            pos, spd, length = q.popleft()
            if (pos, spd) in encountered: continue
            else: encountered.add((pos, spd))
            if pos == target: 
                return length
            if (pos + spd, spd * 2) not in encountered:
                if pos + spd <= 2 * target + 1:
                    q.append((pos + spd, spd * 2, length + 1))
            revSpd = -1 if spd > 0 else 1
            if (pos, revSpd) not in encountered:
                q.append((pos, revSpd, length + 1))
        return -1

class Solution:
    def racecar(self, target: int) -> int:
        record = collections.defaultdict(int)
        cur = (0, 1) #(position, speed)
        queue = collections.deque()
        queue.append(cur)
        record[cur] = 0
        
        while True:
            for _ in range(len(queue)):
                pos, speed = queue.popleft()
                step = record[(pos, speed)]
                if pos == target:
                    return step
                if pos + speed == target:
                    return 1 + step
                
                s1 = (pos + speed, speed * 2)
                s2 = (pos, -1) if speed>0 else (pos, 1)
                
                if s1 not in record:
                    queue.append(s1)
                    record[s1] = step + 1
                if s2 not in record:
                    queue.append(s2)
                    record[s2] = step + 1
        return -1

class Solution:
    def racecar(self, target: int) -> int:
        q = [(0, 1)]
        steps = 0
        visited = set(q)
        while q:
            nxt = []
            for pos, speed in q:
                if pos + speed == target:
                    return steps + 1
                nxt_pos = pos + speed
                nxt_speed = speed * 2
                if (nxt_pos, nxt_speed) not in visited:
                    visited.add((nxt_pos, nxt_speed))
                    nxt.append((nxt_pos, nxt_speed))
                
                nxt_pos = pos
                nxt_speed = -1 if speed > 0 else 1
                if (nxt_pos, nxt_speed) not in visited:
                    visited.add((nxt_pos, nxt_speed))
                    nxt.append((nxt_pos, nxt_speed))
            q = nxt
            steps += 1


class Solution:
    def racecar(self, target: int) -> int:
        if target == 0:
            return 0        
        # BFS solution
        level = 0
        q = deque([(0, 1)]) # tuple of (pos, speed)
        visited = {(0, 1),}
        while q:
            length = len(q)
            for _ in range(length):
                p, s = q.popleft()
                # use A
                new_p, new_s = p + s, 2*s
                if new_p == target:
                    return level + 1
                if (new_p, new_s) not in visited:
                    visited.add((new_p, new_s))
                    q.append((new_p, new_s))
                # use R
                new_p, new_s = p, -s//abs(s)
                if (new_p, new_s) not in visited:
                    visited.add((new_p, new_s))
                    q.append((new_p, new_s))
            level += 1

import collections
class Solution:
    def racecar(self, target: int) -> int:
        # bfs
        q = collections.deque([(0, 0, 1)]) # move, pos, vel
        while q:
            move, pos, vel = q.popleft()
            if pos == target:
                return move            
            # A
            q.append((move+1, pos+vel, vel*2))           
            # R, considered in 4 cases, get rid of excessive search
            if (pos > target and vel > 0) or (pos < target and vel < 0) or (pos + vel > target and vel > 0) or (pos + vel < target and vel < 0):  #reverse
                q.append((move+1, pos, -1 if vel > 0 else 1))

from collections import deque
class Solution:
    def racecar(self, target: int) -> int:
        if target == 0:
            return 0
        visited = set()
        queue = deque()
        queue.append((0, 1))
        visited.add((0, 1))
        step = 1
        
        while queue:
            for _ in range(len(queue)):
                cur_pos, cur_speed = queue.popleft()
                next_pos, next_speed = cur_pos + cur_speed, cur_speed * 2
                if next_pos == target:
                    return step
                if (next_pos, next_speed) not in visited:
                    queue.append((next_pos, next_speed))
                    visited.add((next_pos, next_speed))
                if cur_speed > 0:
                    next_speed = -1
                else:
                    next_speed = 1
                if (cur_pos, next_speed) not in visited:
                    queue.append((cur_pos, next_speed))
                    visited.add((cur_pos, next_speed))
            step += 1
        
        return -1

class Solution:
    def racecar(self, target: int) -> int:
        front = [(0,1)]
        visited = {(0,1):0}
        while front!=[]:
            nf = [];
            for (pos,speed) in front:
                aa = [(pos+speed, speed*2),(pos, -1)] if speed>0 else [(pos+speed, speed*2),(pos, 1)]
                for v in aa:
                    if not v in visited:
                        visited[v] = visited[(pos,speed)]+1
                        nf.append(v)
                        if v[0] == target:
                            return visited[v]
            front = nf


class Solution:
    def racecar(self, target: int) -> int:
        q = [(0, 1)]
        steps = 0
        visited = set(q)
        while q:
            nxt = []
            for pos, speed in q:
                if pos + speed == target:
                    return steps + 1
                if (pos+speed, speed*2) not in visited:
                    visited.add((pos+speed, speed*2))
                    nxt.append((pos+speed, speed*2))
                    
                nxt_speed = -1 if speed > 0 else 1
                if (pos, nxt_speed) not in visited:
                    visited.add((pos, nxt_speed))
                    nxt.append((pos, nxt_speed))
            q = nxt
            steps += 1


class Solution:
    def racecar(self, target: int) -> int:
        queue = deque([(0, 1)])
        dists = {(0, 1): 0}
        while queue:
            x, v = queue.popleft()
            d = dists[(x, v)]
            if x+v == target:
                return d+1
            y, w = x+v, v << 1
            if (y, w) not in dists:
                dists[(y, w)] = d+1
                queue.append((y, w))
            opv = -1 if v > 0 else 1
            if (x, opv) not in dists:
                dists[(x, opv)] = d+1
                queue.append((x, opv)) 

class Solution:
  def __init__(self):
    self.dp = {0: 0}
  
  def racecar(self, t: int) -> int:
    if t in self.dp:
      return self.dp[t]
    n = t.bit_length()
    if 2**n - 1 == t:
      self.dp[t] = n
    else:
      # go pass via n A's, then turn back
      self.dp[t] = self.racecar(2**n - 1 - t) + n + 1
      # stop after (n - 1) A's, turn back, go m A's, then turn back
      for m in range(n - 1):
        self.dp[t] = min(self.dp[t], self.racecar(t - 2**(n - 1) + 2**m) + n + m + 1)
    return self.dp[t]

class Solution:
    def racecar(self, target):
        target *= -1
        q, used = [(0, 0, -1)], {(0, -1)}
        while q:
            cnt, pos, speed = heapq.heappop(q)
            if pos == target:
                return cnt
            elif pos > 20000 or -20000 > pos:
                continue
            if (pos + speed, speed * 2) not in used:
                heapq.heappush(q, (cnt + 1, pos + speed, speed * 2))
                used.add((pos + speed, speed * 2))
            if speed < 0 and (pos, 1) not in used:
                heapq.heappush(q, (cnt + 1, pos, 1))
                used.add((pos, 1))
            elif speed > 0 and (pos, -1) not in used:
                heapq.heappush(q, (cnt + 1, pos, -1))
                used.add((pos, -1))

from collections import deque
class Solution:
    def racecar(self, target: int) -> int:
        
        steps = 0
        queue = deque([(0, 1)])
        cache = {(0,1)}
        while queue:
            for _ in range(len(queue)):
                p, s = queue.popleft()
                if p == target:
                    return steps
                p1,s1 = p+s, s*2
                p2 = p
                s2 = -1 if s > 0 else 1
                if (p1,s1) not in cache:
                    cache.add((p1,s1))
                    queue.append((p1,s1))
                if (p2,s2) not in cache:
                    cache.add((p2,s2))
                    queue.append((p2,s2))
            steps += 1

                
            
            


class Solution:
    def racecar(self, target: int) -> int:
        dq = deque([(0, 1)])
        res = 0
        seen = {(0,1)}
        while dq:
            length = len(dq)
            
            for _ in range(length):
                p, s = dq.popleft()
                
                rs = -1 if s>0 else 1
                for np, ns in [[p+s, 2*s], [p, rs]]:
                    if np==target:
                        return res+1
                    
                    if (np, ns) not in seen:
                        seen.add((np, ns))
                        dq.append((np, ns))
                        
            res += 1

class Solution:
    def racecar(self, target: int) -> int:
        visited = {(0,1)}
        queue = collections.deque()
        queue.append((0,1))
        steps = 0
        while queue:
            size = len(queue)
            for _ in range(size):
                s, v = queue.popleft()
                if s == target: return steps
                # 'A'
                cur_s = s + v
                cur_v = v * 2
                if (cur_s, cur_v) not in visited:
                    queue.append((cur_s, cur_v))
                    visited.add((cur_s, cur_v))
                #'R'
                cur_s = s
                cur_v = -1 if v > 0 else 1
                if (cur_s, cur_v) not in visited:
                    queue.append((cur_s, cur_v))
                    visited.add((cur_s, cur_v))
            steps += 1
            


class Solution:
    def racecar(self, target: int) -> int:
        q = collections.deque()
        q.append((0, 1))
        visited = set()
        visited.add((0, 1))
        
        step = 0
        while q:
            size = len(q)
            for _ in range(size):
                pos, speed = q.popleft()
                if pos == target:
                    return step
                
                # 'A'
                if (pos + speed, speed * 2) not in visited:
                    visited.add((pos + speed, speed * 2))
                    q.append((pos + speed, speed * 2))
                
                # 'R'
                if (pos > target and speed > 0) or (pos < target and speed < 0) or (pos + speed > target and speed > 0) or (pos + speed < target and speed < 0):
                    speed = -1 if speed > 0 else 1
                    if (pos, speed) not in visited:
                        visited.add((pos, speed))
                        q.append((pos, speed))
        
            step += 1
        


class Solution:
    def racecar(self, target: int) -> int:
        q = deque([(0, 1)])
        visited = set([(0, 1)])
        
        step = 0
        while q:
            l = len(q)
            step += 1
            for _ in range(l):
                pos, speed = q.popleft()
                if pos == target:
                    return step - 1
                new_pos, new_speed = pos + speed, speed * 2
                if (new_pos, new_speed) not in visited:
                    q.append((new_pos, new_speed))
                    visited.add((new_pos, new_speed))
                
                new_pos, new_speed = pos, -1 if speed > 0 else 1
                if (new_pos, new_speed) not in visited:
                    q.append((new_pos, new_speed))
                    visited.add((new_pos, new_speed))
        return -1

class Solution:
    def racecar(self, target: int) -> int:
        
        q = [(0,1)]
        vis = {(0,1)}
        ans=0
        while q:
            new_q = []
            for p,s in q:
                if p==target:
                    return ans
                p1,s1 = p+s,2*s
                p2,s2 = p, -1 if s>0 else 1
                if (p1,s1) not in vis:
                    vis.add((p1,s1))
                    new_q.append((p1,s1))
                if (p2,s2) not in vis:
                    vis.add((p2,s2))
                    new_q.append((p2,s2))
            q = new_q
            ans+=1
        return -1


class Solution:
    def racecar(self, target: int) -> int:
        
        q = [(0,1)]
        vis = set([(0,1)])
        ans=0
        while q:
            new_q = []
            for p,s in q:
                if p==target:
                    return ans
                p1,s1 = p+s,2*s
                p2,s2 = p, -1 if s>0 else 1
                if (p1,s1) not in vis:
                    vis.add((p1,s1))
                    new_q.append((p1,s1))
                if (p2,s2) not in vis:
                    vis.add((p2,s2))
                    new_q.append((p2,s2))
            q = new_q
            ans+=1
        return -1


from collections import deque

class Solution:
    def racecar(self, target: int) -> int:
        q = deque([(0, 1, 0)])
        visited = set([(0, 1)])
        while q:
            pos, speed, steps = q.popleft()
            if pos == target:
                return steps
            
            nxt_pos = pos + speed
            nxt_speed = speed * 2
            if (nxt_pos, nxt_speed) not in visited:
                visited.add((nxt_pos, nxt_speed))
                q.append((nxt_pos, nxt_speed, steps+1))
            
            nxt_pos = pos
            nxt_speed = -1 if speed > 0 else 1
            if (nxt_pos, nxt_speed) not in visited:
                visited.add((nxt_pos, nxt_speed))
                q.append((nxt_pos, nxt_speed, steps+1))


class Solution:
    def racecar(self, target: int) -> int:
        # BFS + trim
        if target==0: return 0
        q = {(0,1)} # (pos, speed)
        visited= {(0,1)}
        steps = -1
        while q:
            steps += 1
            next_q = set()
            for pos, speed in q:
                if pos==target: return steps
                # 1. If A
                state_A = (pos+speed, speed*2)
                if state_A not in visited:
                    visited.add(state_A)
                    next_q.add(state_A)
                # 2. If R
                state_R =  (pos, -1 if speed>0 else 1)
                if state_R not in visited:
                    visited.add(state_R)
                    next_q.add(state_R)
            q = next_q
        return steps

class Solution:
    def racecar(self, target: int) -> int:
        stack = collections.deque([(0, 1, 0)])
        seen = set([(0, 1)])
        while stack:
            pos, speed, steps = stack.popleft()
            if pos == target:
                return steps
            
            new = (pos + speed, speed * 2)
            if new not in seen:
                seen.add(new)
                stack.append((new[0], new[1], steps + 1))
            
            
            new = (pos, -1 if speed > 0 else 1)
            if new not in seen:
                seen.add(new)
                stack.append((new[0], new[1], steps + 1))


import numpy as np

class Solution:
    def racecar(self, target: int) -> int:
        def dp(t):
            if ans[t] > 0:
                return ans[t]
            n = int(np.ceil(np.log2(t + 1)))
            if 1 << n == t + 1:
                ans[t] = n
                return ans[t]
            ans[t] = n + 1 + dp((1 << n) - 1 - t)
            for m in range(n):
                cur = (1 << (n - 1)) - (1 << m)
                ans[t] = min(ans[t], n + m + 1 + dp(t - cur))
            return ans[t]
            
        ans = [0 for _ in range(target + 1)]
        return dp(target)

class Solution:
    def racecar(self, T: int, depth = 0) -> int:
        q = collections.deque([[ 0, 1 ]])
        seen = set('0,1')
        while True:
            k = len(q)
            while k:
                [ pos, vel ] = q.popleft()
                if pos == T:
                    return depth  # \\U0001f3af target T found
                cand = []
                if abs(T - (pos + vel) < T):
                    cand.append([ pos + vel, 2 * vel ])
                cand.append([ pos, 1 if vel < 0 else -1 ])
                for pos, vel in cand:
                    if f'{pos},{vel}' not in seen:
                        q.append([ pos, vel ])
                        seen.add(f'{pos},{vel}')
                k -= 1
            depth += 1
        return -1
                


from collections import deque
class Solution:
    def racecar(self, target: int) -> int:
        dic = {}
        qu = deque([(0,1)])
        dic[(0, 1)] = 0
        while qu:
            front = qu.popleft()
            pos, spd = front
            if pos == target:
                return dic[front]
            
            speedup = (pos + spd, spd*2)
            if speedup not in dic:
                qu.append(speedup)
                dic[speedup] = dic[front] + 1
            
            fwd2bwd = (pos, -1)
            if spd > 0 and fwd2bwd not in dic:
                qu.append(fwd2bwd)
                dic[fwd2bwd] = dic[front] + 1
                
            bwd2fwd = (pos, 1)
            if spd < 0 and (pos, 1) not in dic:
                qu.append((pos, 1))
                dic[bwd2fwd] = dic[front] + 1
            
            
            


class Solution:
    def racecar(self, target: int) -> int:
        q = collections.deque()
        q.append((0, 1))
        visited = set()
        visited.add((0, 1))
        
        step = 0
        while q:
            size = len(q)
            for _ in range(size):
                pos, speed = q.popleft()
                if pos == target:
                    return step
                
                # 'A'
                if (pos + speed, speed * 2) not in visited:
                    visited.add((pos + speed, speed * 2))
                    q.append((pos + speed, speed * 2))
                
                # 'R'
                if speed > 0:
                    speed = -1
                else:
                    speed = 1
                if (pos, speed) not in visited:
                    visited.add((pos, speed))
                    q.append((pos, speed))
        
            step += 1
        


class Solution:
    def racecar(self, T: int) -> int:
        q = collections.deque([[ 0, 1 ]])
        seen = set('0,1')
        depth = 0
        while True:
            k = len(q)
            while k:
                [ pos, vel ] = q.popleft()
                if pos == T:
                    return depth  # \\U0001f3af target T found
                cand = []
                if abs(T - (pos + vel) < T):
                    cand.append([ pos + vel, 2 * vel ])
                cand.append([ pos, 1 if vel < 0 else -1 ])
                for pos, vel in cand:
                    if f'{pos},{vel}' not in seen:
                        q.append([ pos, vel ])
                        seen.add(f'{pos},{vel}')
                k -= 1
            depth += 1
        return -1

class Solution:
    def racecar(self, target: int) -> int:
        queue = deque([(0, 1, 0)])
        seen = {(0, 1)}
        while queue:
            pos, speed, cost = queue.popleft()
            if pos == target:
                return cost
            
            # A
            new_pos, new_speed = pos + speed, speed * 2
            if (new_pos, new_speed) not in seen:
                seen.add((new_pos, new_speed))
                queue.append((new_pos, new_speed, cost + 1)) # A
                
            # R
            reverse_speed = -1 if speed > 0 else 1
            if (pos, reverse_speed) not in seen:
                seen.add((pos, reverse_speed))
                queue.append((pos, reverse_speed, cost + 1))
            
                    
            
        


class Solution:
    def racecar(self, T: int, depth = 0) -> int:
        q = collections.deque([[ 0, 1 ]])
        seen = set('0,1')
        while True:
            k = len(q)
            while k:
                [ pos, vel ] = q.popleft()
                if pos == T:
                    return depth  # \\U0001f3af target T found
                cand = []
                if abs(T - (pos + vel) < T):
                    cand.append([ pos + vel, 2 * vel ])
                cand.append([ pos, 1 if vel < 0 else -1 ])
                for pos, vel in cand:
                    if f'{pos},{vel}' not in seen:
                        q.append([ pos, vel ])
                        seen.add(f'{pos},{vel}')
                k -= 1
            depth += 1
        return -1

class Solution:
    def racecar(self, target: int) -> int:
        queue = [(0, 1)]
        step = 0
        visited = {(0, 1)}
        while queue:
            tmp = queue
            queue = []
            for pos, speed in tmp:
                if pos == target:
                    return step
                
                if not (pos + speed, speed * 2) in visited:
                    queue.append((pos + speed, speed * 2))
                    visited.add((pos + speed, speed * 2))
                speed = -1 if speed > 0 else 1
                if not (pos, speed) in visited:
                    queue.append((pos, speed))
                    visited.add((pos, speed))
            step += 1
        
        return 0

class Solution:
    def racecar(self, target: int) -> int:
        pq = [(0, 0, -1)]
        visited = set([(0, -1)])
        
        while pq:
            steps, pos, speed = heapq.heappop(pq)
            
            next_steps = steps + 1
            next_pos = pos + speed
            next_speed = speed * 2
            
            if -next_pos == target:
                return next_steps
            
            if -next_pos < 2 * target and -next_speed < 2 * target and not (next_pos, next_speed) in visited:
                heapq.heappush(pq, (next_steps, next_pos, next_speed))
                visited.add((next_pos, next_speed))
            
            if speed < 0 and not (pos, 1) in visited:
                heapq.heappush(pq, (next_steps, pos, 1))
                visited.add((pos, 1))
            elif speed > 0 and not (pos, -1) in visited:
                heapq.heappush(pq, (next_steps, pos, -1))
                visited.add((pos, -1))
        return -1

class Solution:
    def racecar(self, target: int) -> int:
        nodes = [(0, 1)]
        seen, length = set([(0, 1)]), 0
        while nodes:
            new_nodes = []
            for pos, speed in nodes:
                if pos == target:
                    return length
                # A
                for new_pos, new_speed in [
                    (pos + speed, speed * 2),
                    (pos, -1 if speed > 0 else 1),
                ]:
                    if (new_pos, new_speed) not in seen:
                        seen.add((new_pos, new_speed))
                        new_nodes.append((new_pos, new_speed))
            length += 1
            nodes = new_nodes


class Solution:
    def racecar(self, target: int) -> int:
        # dp[i] solution for target = i
        dp = [ 0, 1, 4 ] + [ float('inf') ] * (target - 2)
        for i in range(3, target + 1):
            k = math.log2(i + 1)
            if int(k) == k:
                dp[i] = int(k)
                continue
            k = int(k)
            # 1. go to 2 ** m - 1 and R^2 costing m + 2 (m <= k)
            for m in range(0, k):
                dp[i] = min(dp[i], dp[i - 2 ** k + 2 ** m] + k + m + 2)
            # 2. go to 2 ** (k + 1) - 1 and R costing k + 1 + 1 
            if i > 2 ** (k + 1) - 1 - i:
                dp[i] = min(dp[i], dp[2 ** (k + 1) - 1 - i] + k + 1 + 1)
        return dp[target]


class Solution:
    def racecar(self, target: int) -> int:
        
        q = collections.deque([])
        q.append((0, 1, 0))
        visited = set()
        visited.add((0, 1))
        
        while q:
            pos, speed, steps = q.popleft()
            
            if pos == target:
                return steps
            
            if (pos + speed, speed * 2) not in visited:
                q.append((pos + speed, speed * 2, steps + 1))
                visited.add((pos + speed, speed * 2))
            
            if speed > 0:
                if (pos, -1) not in visited:
                    q.append((pos, -1, steps + 1))
                    visited.add((pos, -1))
            else:
                if (pos, 1) not in visited:
                    q.append((pos, 1, steps + 1))
                    visited.add((pos, 1))
        return -1


from collections import deque

class Solution:
    def racecar(self, target: int) -> int:
        q = deque([(0, 1)])
        visited = set([(0, 1)])
        res = 0
        while q:
            size = len(q)
            for _ in range(size):
                pos, speed = q.popleft()
                if pos == target:
                    return res
                if (pos + speed, speed * 2) not in visited:
                    q.append((pos + speed, speed * 2))
                    visited.add((pos + speed, speed * 2))
                speed = 1 if speed < 0 else -1
                if (pos, speed) not in visited:
                    q.append((pos, speed))
                    visited.add((pos ,speed))
            res += 1
        return res

class Solution:
    def racecar(self, target: int) -> int:
        
        queue = [[(0, 1)]] #(position, speed)
        visited = {(0,1)}
        
        seq = 0
        while queue:
            curLevel = queue.pop()
            newLevel = []
            
            for pos, speed in curLevel:
                if pos == target:
                    return seq
                
                for newPos, newSpeed in [(pos+speed, speed*2), (pos, -1 if speed > 0 else 1)]:
                    if (newPos, newSpeed) not in visited:
                        visited.add((newPos, newSpeed))
                        newLevel.append((newPos, newSpeed))
                
            if newLevel:
                queue.append(newLevel)
                seq += 1
        
        return -1

class Solution:
    def racecar(self, target: int) -> int:
        initial_state = (0, 1, 0)
        bfs = [initial_state]
        valid_actions = ['A', 'R']
        visited = set([(0, 1)])
        for position, speed, count in bfs:
            if position == target:
                return count

            for action in valid_actions:
                if action == 'A':
                    _position = position + speed
                    _speed = speed * 2


                elif action == 'R':
                    _position = position
                    if speed > 0:
                        _speed = -1
                    else:
                        _speed = 1

                if (_position, _speed) not in visited:
                    visited.add((_position, _speed))
                    bfs.append((_position, _speed, count+1))

        return -1

class Solution:
    def racecar(self, target: int) -> int:
        # bfs
        bq=collections.deque([(0,1,0)])
        visited=set((0,1))
        while bq:
            p,s,step= bq.popleft()
            if p==target:
                return step
            if (p+s,2*s) not in visited:
                bq.append((p+s,2*s,step+1))
                visited.add((p+s,2*s))
            ns= 1 if s<0 else -1
            if (p,ns) not in visited:
                bq.append((p,ns,step+1))
                visited.add((p,ns))


class Solution:
    def racecar(self, target: int) -> int:
        barrier = 2 * target
        heap = [[0,0,1]]
        seen = {}
        while heap:
            step, position, speed = heappop(heap)
            
            if position == target:
                return step - 1
            
            if (position,speed) in seen and seen[position,speed] <= step:
                continue
            seen[position,speed] = step

            k = 0
            while True:
                new_pos = position + speed * (2 ** k - 1)

                if -barrier <= new_pos <= barrier:
                    heappush(heap, [step + k + 1, new_pos, -speed])
                else:
                    break
                k += 1


class Solution:
    def racecar(self, target: int) -> int:
        barrier = 2 * target
        heap = [[0,0,1]]
        seen = {}
        while heap:
            step, position, speed = heappop(heap)
            
            if position == target:
                return step - 1
            
            if (position,speed) in seen and seen[position,speed] <= step:
                continue
            seen[position,speed] = step

            k = 0
            while True:
                new_pos = position + speed * (2 ** k - 1)

                if -barrier <= new_pos <= barrier:
                    heappush(heap, [step + k + 1, new_pos, -speed])
                else:
                    break
                    
                k += 1


class Solution:
    def racecar(self, target: int) -> int:
        max_step = int(log(target,2)) + 2
        barrier = 2 * target + 2
        heap = [[i + 1, 0 + (2 ** i - 1), -1] for i in range(max_step+1)]
        seen = {}
        while heap:
            step, position, speed = heappop(heap)
            
            if position == target:
                return step - 1
            
            if (position,speed) in seen and seen[position,speed] <= step:
                continue
            seen[position,speed] = step

            k = 0
            while True:
                new_pos = position + speed * (2 ** k - 1)

                if -barrier <= new_pos <= barrier:
                    heappush(heap, [step + k + 1, new_pos, -speed])
                else:
                    break
                    
                k += 1


class Solution:
    def racecar(self, target: int) -> int:
        barrier = 2 * target
        heap = [[0,0,1]]
        seen = set()
        while heap:
            step, position, speed = heappop(heap)
            
            if position == target:
                return step - 1
            
            if (position,speed) in seen:
                continue
            seen.add((position,speed))

            k = 0
            while True:
                new_pos = position + speed * (2 ** k - 1)

                if -barrier <= new_pos <= barrier:
                    heappush(heap, [step + k + 1, new_pos, -speed])
                else:
                    break
                k += 1


class Solution:
    def racecar(self, target: int) -> int:
        dp = [0, 1, 4] + [float('inf')] * target
        for t in range(3, target + 1):
            k = t.bit_length()
            if t == 2**k - 1:
                dp[t] = k
                continue
            for j in range(k - 1):
                dp[t] = min(dp[t], dp[t - 2**(k - 1) + 2**j] + k - 1 + j + 2)
            if 2**k - 1 - t < t:
                dp[t] = min(dp[t], dp[2**k - 1 - t] + k + 1)
        return dp[target]

class Solution:
    def racecar(self, target: int) -> int:
        dp = [0,1,4] + [float('inf')] * target
        for t in range(3, target+1):
            k = t.bit_length()
            if t == 2**k-1:
                dp[t] = k
                continue
            for j in range(k-1):
                dp[t] = min(dp[t], dp[t - 2**(k - 1) + 2**j] + k - 1 + j + 2)
                # dp[t] = min(dp[t], dp[t - 2**(k - 1) + 1] + k - 1 + j + 2)
            if 2**k - 1 - t < t:
                dp[t] = min(dp[t], dp[2**k - 1 - t] + k + 1)
        return dp[target]


class Solution:
    def racecar(self, target: int) -> int:
        dp = [0, 1, 4] + [float('inf')] * target
        for i in range(3, target+1):
            k = i.bit_length()
            if i == 2**k-1:
                dp[i] = k
                continue
            
            for j in range(k-1):
                dp[i] = min(dp[i], dp[i-2**(k-1) + 2**j] + k-1+j+2)
            if 2**k-1-i < i:
                dp[i] = min(dp[i], dp[2**k-1-i]+k+1)
        return dp[target]

class Solution(object):
    def racecar(self, target):
        dp = [0, 1, 4] + [float('inf')] * target
        for t in range(3, target + 1):
            k = t.bit_length()
            if t == 2**k - 1:
                dp[t] = k
                continue
            for j in range(k - 1):
                dp[t] = min(dp[t], dp[t - 2**(k - 1) + 2**j] + k - 1 + j + 2)
            if 2**k - 1 - t < t:
                dp[t] = min(dp[t], dp[2**k - 1 - t] + k + 1)
        return dp[target]

class Solution:
    def racecar(self, target: int) -> int:
        # from answers:
        # Dojkstra's
        '''
        K = target.bit_length() + 1
        barrier = 1 << K
        pq = [(0, target)]
        dist = [float('inf')] * (2 * barrier + 1)
        dist[target] = 0

        while pq:
            steps, targ = heapq.heappop(pq)
            if dist[targ] > steps: continue

            for k in range(K+1):
                walk = (1 << k) - 1
                steps2, targ2 = steps + k + 1, walk - targ
                if walk == targ: steps2 -= 1 #No \"R\" command if already exact

                if abs(targ2) <= barrier and steps2 < dist[targ2]:
                    heapq.heappush(pq, (steps2, targ2))
                    dist[targ2] = steps2

        return dist[0]
        '''
        # Dynamic programming
        dp = [0, 1, 4] + [float('inf')] * target
        for t in range(3, target + 1):
            k = t.bit_length()
            if t == 2**k - 1:
                dp[t] = k
                continue
            for j in range(k - 1):
                dp[t] = min(dp[t], dp[t - 2**(k - 1) + 2**j] + k - 1 + j + 2)
            if 2**k - 1 - t < t:
                dp[t] = min(dp[t], dp[2**k - 1 - t] + k + 1)
        return dp[target]


class Solution:
    def racecar(self, target: int) -> int:
        if target == 0:
            return 0
        
        f = [None] * (target + 1)
        
        f[0] = 0
        
        for i in range(1, target + 1):
            f[i] = float('inf')
            
            k = i.bit_length()
            
            if i == 2 ** k - 1:
                f[i] = k
                continue
                
            # underspeed
            for j in range(k - 1):
                f[i] = min(f[i], f[i - 2 ** (k - 1) + 2 ** j] + k - 1 + j + 2)
                
            # overspeed
            if 2 ** k - 1 - i < i:
                f[i] = min(f[i], f[2 ** k - 1 - i] + k + 1)
        return f[target]

class Solution:
    def racecar(self, target: int) -> int:
        LIMIT = 2**(target.bit_length()) - 1
        dp = [0, 1, 4] + [float('INF')]*(LIMIT-2)
        for t in range(3, target+1):
            k = t.bit_length()
            if t == 2**k - 1:
                dp[t] = k
                continue
            # not cross t, but first reverse to position t - 2**(k-1) + 2**j, then reverse and accelerate to t
            for j in range(k):
                dp[t] = min(dp[t], dp[t - 2**(k-1) + 2**j] + k + j + 1)
            # first cross t to 2**k - 1, then reverse to t
            dp[t] = min(dp[t], k + 1 + dp[2**k - 1 - t])
        
        return dp[target]

class Solution:
    def __init__(self):
        self._dp = {0:0}

    def racecar(self, target):
        # 车子初始位置0，速度1
        # 遇到A，position += speed并且speed *= 2
        # 遇到R，speed = -1如果当前speed是1；speed = 1如果
        # 给定最终的位置target，问最短的sequence（由A和R组成）能够到达target
        if target == 0:
            return 0
        if target == 1:
            return 1
        if target == 2:
            return 4
        # 如果一直踩油门的话(连续3个A)
        # 则会到达0 -> 1 -> 3 -> 7
        #         k=1  k=2  k=3
        dp = [2 ** 31 - 1] * (target + 1)
        dp[0], dp[1], dp[2] = 0, 1, 4
        for t in range(3, target + 1):
            k = t.bit_length()
            if t == 2 ** k - 1:
                # t = 7, 二进制111, k = 3
                # 此时表明踩3脚油门就能到了
                dp[t] = k
                continue
            
            # 情况1：走2 ** (k - 1)的距离
            # 然后用一个R和m个A去往回走
            # 这时候已经走了k - 1 + 1 + m + 1步（即A**(k - 1)RA**(m)R步)
            # 然后去dp里找剩余的步数t - 2 ** (k - 1) + 2 ** m
            for m in range(k - 1):
                # 注意：后面的k - 1 + m + 2是当前走了这么多步
                dp[t] = min(dp[t], dp[t - 2 ** (k - 1) + 2 ** m] + k - 1 + m + 2)
            
            # 情况2：直接2 ** k步
            #（已经走了最大的k + 1步, 就是在最后min函数括号里加的那一部分，加1是指一个R）
            # 然后再往回走
            # 走了k + 1步距离就是2 ** k - 1，这个距离已经超越了t
            # 所以还要继续走2 ** k - 1 - t步才能走到t
            if 2 ** k - 1 - t > 0:
                dp[t] = min(dp[t], dp[2 ** k - 1 - t] + k + 1)
        return dp[target]
        


class Solution:
    def racecar(self, target):
        # 车子初始位置0，速度1
        # 遇到A，position += speed并且speed *= 2
        # 遇到R，speed = -1如果当前speed是1；speed = 1如果
        # 给定最终的位置target，问最短的sequence（由A和R组成）能够到达target
        if target == 0:
            return 0
        if target == 1:
            return 1
        if target == 2:
            return 4
        # 如果一直踩油门的话(连续3个A)
        # 则会到达0 -> 1 -> 3 -> 7
        #         k=1  k=2  k=3
        dp = [2 ** 31 - 1] * (target + 1)
        dp[0], dp[1], dp[2] = 0, 1, 4
        for t in range(3, target + 1):
            k = t.bit_length()
            if t == 2 ** k - 1:
                # t = 7, 二进制111, k = 3
                # 此时表明踩3脚油门就能到了
                dp[t] = k
                continue
            
            # 此时必定 2 ** (k - 1) <= t <= 2 ** (k + 1)
            assert 2 ** (k - 1) <= t <= 2 ** (k + 1)

            # 情况1：走k - 1步，还没到t，回头再回头的策略
            # 然后用一个R和m个A去往回走
            # 这时候已经走了k - 1 + 1 + m + 1步（即A**(k - 1)RA**(m)R步)
            # 然后去dp里找剩余的步数t - 2 ** (k - 1) + 2 ** m
            for m in range(k - 1):
                # 注意：后面的k - 1 + m + 2是当前走了这么多步
                dp[t] = min(dp[t], dp[t - 2 ** (k - 1) + 2 ** m] + k - 1 + m + 2)
            
            # 情况2：直接k步，假设能够超过t，就采取再回头的策略
            #（已经走了k步, 就是在最后min函数括号里加的那一部分，加1是指一个R）
            # 然后再往回走
            # 走了k步距离就是2 ** k - 1，这个距离已经超越了t
            # 所以还要继续走2 ** k - 1 - t步才能走到t
            if 2 ** k - 1 - t > 0:
                dp[t] = min(dp[t], dp[2 ** k - 1 - t] + k + 1)
        return dp[target]
        


from collections import deque

class Solution:
    def racecar(self, target):
        # 车子初始位置0，速度1
        # 遇到A，position += speed并且speed *= 2
        # 遇到R，speed = -1如果当前speed是1；speed = 1如果
        # 给定最终的位置target，问最短的sequence（由A和R组成）能够到达target
        if target == 0:
            return 0
        if target == 1:
            return 1
        if target == 2:
            return 4
        # 如果一直踩油门的话(连续3个A)
        # 则会到达0 -> 1 -> 3 -> 7
        #         k=1  k=2  k=3
        # dp[t]的定义是到达t位置最少需要走多少步
        dp = [2 ** 31 - 1] * (target + 1)
        dp[0], dp[1], dp[2] = 0, 1, 4
        for t in range(3, target + 1):
            k = t.bit_length()
            if t == 2 ** k - 1:
                # t = 7, 二进制111, k = 3
                # 此时表明踩3脚油门就能到了
                dp[t] = k
                continue
            
            # 此时必定 2 ** (k - 1) <= t <= 2 ** (k + 1)
            assert 2 ** (k - 1) <= t <= 2 ** (k + 1)

            # 情况1：走k - 1步，还没到t，回头再回头的策略
            # 然后用一个R和m个A去往回走
            # 这时候已经走了k - 1 + 1 + m + 1步（即A**(k - 1)RA**(m)R步)
            # 然后去dp里找剩余的步数t - 2 ** (k - 1) + 2 ** m
            for m in range(k - 1):
                # 注意：后面的k - 1 + m + 2是当前走了这么多步
                dp[t] = min(dp[t], dp[t - 2 ** (k - 1) + 2 ** m] + k - 1 + m + 2)
            
            # 情况2：直接k步，假设能够超过t，就采取再回头的策略
            #（已经走了k步, 就是在最后min函数括号里加的那一部分，加1是指一个R）
            # 然后再往回走
            # 走了k步距离就是2 ** k - 1，这个距离已经超越了t
            # 所以还要继续走2 ** k - 1 - t步才能走到t
            if 2 ** k - 1 - t > 0:
                dp[t] = min(dp[t], dp[2 ** k - 1 - t] + k + 1)
        return dp[target]
        
        # BFS解法，非最优，但是好想
#         queue = deque([(0, 1)])
#         # 状态是(location, speed)
#         visited = set([(0, 1)])
        
#         res = 0
#         while queue:
#             q_len = len(queue)
#             for _ in range(q_len):
#                 curr_pos, curr_speed = queue.popleft()
#                 if curr_pos == target:
#                     return res
                
#                 # case-1: 当前选择A
#                 new_pos = curr_pos + curr_speed
#                 new_speed = 2 * curr_speed
#                 if (new_pos, new_speed) not in visited:
#                     queue.append((new_pos, new_speed))
#                     visited.add((new_pos, new_speed))
                
#                 # case-2: 当前选择R
#                 new_pos = curr_pos
#                 new_speed = -1 if curr_speed > 0 else 1
#                 if (new_pos, new_speed) not in visited:
#                     queue.append((new_pos, new_speed))
#                     visited.add((new_pos, new_speed))
#             res += 1
            
#         return res


from collections import deque

class Solution:
    def racecar(self, target: int) -> int:
        queue = deque([(0, 1)]) # position, speed
        level = 0
        while True:
            size = len(queue)
            for _ in range(size):
                position, speed = queue.popleft()
                if position == target:
                    return level
                queue.append((position + speed, speed * 2))
                if position + speed > target and speed > 0 or position + speed < target and speed < 0:
                    queue.append((position, -1 if speed > 0 else 1))
            level += 1

class Solution:
    def racecar(self, target: int) -> int:
        f = [None] * (target + 1)
        
        f[0] = 0

        for i in range(1, target + 1):
            f[i] = float('inf')
            
            k = i.bit_length()
            
            if i == 2**k - 1:
                f[i] = k
                continue
            
            # underspeed
            for j in range(k - 1):
                f[i] = min(f[i], f[i - 2**(k - 1) + 2**j] + k - 1 + j + 2)
            
            # overspeed
            if 2**k - 1 - i < i:
                f[i] = min(f[i], f[2**k - 1 - i] + k + 1)
        return f[target]
    
#         f = [None] * (target + 1)
        
#         f[0] = 0
        
#         for i in range(1, target + 1):
#             f[i] = float('inf')
            
#             n = len(bin(i)[2:])
            
#             if 2**n - 1 == i:
#                 f[i] = n
#                 continue
                
#             # overspeed
#             f[i] = f[2**n - 1 - i] + n + 1 # reverse once
            
#             # underspeed
#             for j in range(0, n):
#                 gap = 1 << j - 1
#                 f[i] = min(f[i], f[i - 2**(n - 1) + gap] + n + j + 1) # reverse twice
#         return f[target]
            
        
        
#         int[] f = new int[target + 1];
#         for (int i = 1; i <= target; i++){
#             int bound = (Integer.highestOneBit(i) << 1) - 1;
#             int n = Integer.bitCount(bound);
#             if (i == bound){
#                 f[i] = n;
#                 continue;
#             }
#             // overspeed
#             f[i] = f[bound - i] + n + 1; // Reverse once
#             // underspeed
#             bound >>= 1;
#             for (int j = 0; j < n; j++){
#                 int gap = (1 << j) - 1;
#                 f[i] = Math.min(f[i], f[i - bound + gap] + n + j + 1); // Reverse twice
#             }
#         }
#         return f[target];
#     }
# }


class Solution:
    def racecar(self, target):
        dp = [0, 1, 4] + [float('inf')] * target
        for t in range(3, target + 1):
            k = t.bit_length()
            if t == 2**k - 1:
                dp[t] = k
                continue
            for j in range(k - 1):
                dp[t] = min(dp[t], dp[t - 2**(k - 1) + 2**j] + k - 1 + j + 2)
            if 2**k - 1 - t < t:
                dp[t] = min(dp[t], dp[2**k - 1 - t] + k + 1)
        return dp[target]
# 比较难的一道题目，想了几天无果看了官方给的题解，还是很巧妙的。
# 用Ak表示k次连续的A，首先结尾一定不是R，开头的RAk可以放到最后。
# 那么最终指令应该形如Ak1RAk2R…RAkn。
# 容易得到奇数的ki与偶数的ki都是单调递减的，且各不相同。
# 并且到达或者超过目标位置之后继续执行A是没有意义的。
# 因此就有了DP的做法，如果下标位置是2k−1，那么可以直接Ak达到。
# 否则有两种情况，一是拐两次到达，正面一定有一次最大限度的2k−1，外加返回走j步（枚举j）。
# 二是直接走刚好超过2k−1，回走到终点。

#     def racecar(self, target: int) -> int:
#         # 0 -> 1 -> 3 -> 7 - > 15
#         # 1 -> 2 -> 4 -> 8 -> 16
#         # 从 0 出发，每次可以 R 或 A两个方向，选择。
#         # 可以记录每次到达的状态，
#         # BFS
        
#         d = deque([(0, 0, 1)])
#         visited = collections.defaultdict(set)
#         visited[0].add(1)
#         ans = float('inf')
#         flag = 0
#         while d:
#             flag += 1
#             # print(\"flag=\", flag,\", d=\", d)
#             l = len(d)
#             while l:
#                 l -= 1
#                 cur = d.popleft()
#                 # print(\"cur=\", cur)
#                 pos, cost, speed = cur
#                 if pos == target:
#                     ans = min(ans, cost)
#                     # continue
#                     return cost
#                 # use R
#                 cost += 1
#                 if 1:
#                     newspeed = -1 if speed > 0 else 1
#                     if not ((pos in visited and newspeed in visited[pos]) or (pos <= 0)):
#                         # print(\"past=\", cur,\", add=\", (pos, cost, -1))
#                         d.append(((pos, cost, newspeed)))
#                         visited[pos].add(newspeed)
#                         # 这里 if 里 break 不要瞎用，会跳出 while l 这个循环的。
#                 # use A
#                 if 1:
#                     if not (( speed in visited and (cost, speed * 2) in visited[pos]) or (pos + speed > target * 2) or (pos + speed <= 0)):
                        
#                         # print(\"past=\", cur,\", add=\", (pos + speed, cost, speed * 2))
#                         d.append((pos + speed, cost, speed * 2))
#                         visited[pos].add(speed * 2)
#         return
                
#   # BFS 搞了半天，终于结束了。注意要剪枝。
# # 1. 首先 visited 加入的是 pos 和 speed。
# # 2. 第二是 位置不能超过 target * 2 。因为 如果超过了 target * 2那么要倒车，倒车从头开始，也要 走 target。这是 不合算的。 
# # 3. 速度不能超过 2*target。  （可以不要）
# # 4. 不要 pos <0 的位置。
#         # pos    0 1 3 2 3
#         # speed  1 2 -1 1


class Solution:
    def racecar(self, target: int) -> int:
        queue = collections.deque()
        visited = set()
        queue.append((0, 1))
        visited.add((0, 1))
        steps = 0
        while queue:
            size = len(queue)
            for i in range(size):
                pos, speed = queue.popleft()
                if pos == target:
                    return steps
                # Option 1: do acceleration, if it is not counter productive.
                next_pos = pos + speed
                if 0 < next_pos < 2 * target:
                    next_state = (next_pos, 2 * speed)
                    if next_state not in visited:
                        visited.add(next_state)
                        queue.append(next_state)
                # Option 2: do reverse.
                next_speed = -1 if speed > 0 else 1
                next_state = (pos, next_speed)
                if next_state not in visited:
                    visited.add(next_state)
                    queue.append(next_state)
            steps += 1
        return -1

class Solution:
    def racecar(self, target):
        # 车子初始位置0，速度1
        # 遇到A，position += speed并且speed *= 2
        # 遇到R，speed = -1如果当前speed是1；speed = 1如果
        # 给定最终的位置target，问最短的sequence（由A和R组成）能够到达target
        if target == 0:
            return 0
        if target == 1:
            return 1
        if target == 2:
            return 4
        # 如果一直踩油门的话(连续3个A)
        # 则会到达0 -> 1 -> 3 -> 7
        #         k=1  k=2  k=3
        dp = [2 ** 31 - 1] * (target + 1)
        dp[0], dp[1], dp[2] = 0, 1, 4
        for t in range(3, target + 1):
            k = t.bit_length()
            if t == 2 ** k - 1:
                # t = 7, 二进制111, k = 3
                # 此时表明踩3脚油门就能到了
                dp[t] = k
                continue
            
            # 此时必定 2 ** (k - 1) <= t <= 2 ** (k + 1)
            assert 2 ** (k - 1) <= t <= 2 ** (k + 1)

            # 情况1：走2 ** (k - 1)的距离
            # 然后用一个R和m个A去往回走
            # 这时候已经走了k - 1 + 1 + m + 1步（即A**(k - 1)RA**(m)R步)
            # 然后去dp里找剩余的步数t - 2 ** (k - 1) + 2 ** m
            for m in range(k - 1):
                # 注意：后面的k - 1 + m + 2是当前走了这么多步
                dp[t] = min(dp[t], dp[t - 2 ** (k - 1) + 2 ** m] + k - 1 + m + 2)
            
            # 情况2：直接2 ** k步
            #（已经走了最大的k + 1步, 就是在最后min函数括号里加的那一部分，加1是指一个R）
            # 然后再往回走
            # 走了k + 1步距离就是2 ** k - 1，这个距离已经超越了t
            # 所以还要继续走2 ** k - 1 - t步才能走到t
            if 2 ** k - 1 - t > 0:
                dp[t] = min(dp[t], dp[2 ** k - 1 - t] + k + 1)
        return dp[target]
        


class Solution:
    def racecar(self, target: int) -> int:
        a,d,m,s=[(0,1)],set([(0,1)]),2*target,0
        while 1:
            b,s=[],s+1
            for i,j in a:
                ii,jj,k=i+j,2*j,-1 if j>0 else 1
                if ii==target: return s
                if (ii,jj) not in d and 0<ii<m:
                    b.append((ii,jj))
                    d.add((ii,jj))
                if (i,k) not in d:
                    b.append((i,k))
                    d.add((i,k))
            a=b

class Solution:
    def __init__(self):
        self._dp = {0:0}

    def racecar(self, target):
        # 车子初始位置0，速度1
        # 遇到A，position += speed并且speed *= 2
        # 遇到R，speed = -1如果当前speed是1；speed = 1如果
        # 给定最终的位置target，问最短的sequence（由A和R组成）能够到达target
        # dp = [0, 1, 4] + [2 ** 31 - 1] * target
        if target == 0:
            return 0
        if target == 1:
            return 1
        if target == 2:
            return 4
        dp = [2 ** 31 - 1] * (target + 1)
        dp[0], dp[1], dp[2] = 0, 1, 4
        for t in range(3, target + 1):
            k = t.bit_length()
            if t == 2 ** k - 1:
                dp[t] = k
                continue
            
            # 情况1：走2 ** (k - 1)的距离
            # 然后用一个R和m个A去往回走
            # 这时候已经走了(k - 1) + 1 + (m - 1) + 1 + 2步（即A**(k - 1)RA**(m - 1)R
            # 然后去dp里找剩余的步数t - 2 ** (k - 1) + 2 ** m
            for m in range(k - 1):
                # 注意：后面的k - 1 + j + 2是当前走了这么多步
                dp[t] = min(dp[t], dp[t - 2 ** (k - 1) + 2 ** m] + k - 1 + m + 2)
            
            # 情况2：直接2 ** k步（已经走了最大的k + 1步, 就是在最后min函数括号里加的那一部分，加1是指一个R），然后再往回走
            # 走了k + 1步距离就是2 ** k - 1，这个距离已经超越了t
            # 所以还要继续走2 ** k - 1 - t步才能走到t
            if 2 ** k - 1 - t > 0:
                dp[t] = min(dp[t], dp[2 ** k - 1 - t] + k + 1)
        return dp[target]
        


from collections import deque
class Solution:
    def racecar(self, target: int) -> int:
        queue = deque([(0,1)]) # start with pos 0, speed 1
        visited = set((0,1))
        level = 0
        while queue:
          num = len(queue)
          for _ in range(num):
            cur_pos, cur_speed = queue.popleft()
            if cur_pos == target:
              return level
            # accelerate instruction
            nex_acc = (cur_pos + cur_speed, cur_speed*2)
            if nex_acc not in visited and 0 < nex_acc[0] < target*2:
              queue.append(nex_acc)
              visited.add(nex_acc)
            nex_rev = (cur_pos, -1 if cur_speed > 0 else 1)
            if nex_rev not in visited and 0 < nex_rev[0] < target*2:
              queue.append(nex_rev)
              visited.add(nex_rev)
          level += 1
        return -1
              


class Solution:
    def racecar(self, target: int) -> int:
        q = deque([(0, 1)])
        visited = set([(0, 1)])
        
        step = 0
        while q:
            l = len(q)
            step += 1
            for _ in range(l):
                pos, speed = q.popleft()
                if pos == target:
                    return step - 1
                new_pos, new_speed = pos + speed, speed * 2
                if (new_pos, new_speed) not in visited and 0 < new_pos <= target * 2:
                    q.append((new_pos, new_speed))
                    visited.add((new_pos, new_speed))
                
                new_pos, new_speed = pos, -1 if speed > 0 else 1
                if (new_pos, new_speed) not in visited and 0 < new_pos <= target * 2:
                    q.append((new_pos, new_speed))
                    visited.add((new_pos, new_speed))
        return -1

class Solution:
    def racecar(self, target: int) -> int:
        if target == 0:
            return 0        
        # BFS solution
        level = 0
        q = deque([(0, 1)]) # tuple of (pos, speed)
        visited = {(0, 1),}
        while q:
            length = len(q)
            for _ in range(length):
                p, s = q.popleft()
                # use A
                new_p, new_s = p + s, 2*s
                if new_p == target:
                    return level + 1
                if 0 < new_p < 2* target and (new_p, new_s) not in visited:
                    visited.add((new_p, new_s))
                    q.append((new_p, new_s))
                # use R
                new_p, new_s = p, -s//abs(s)
                if 0 < new_p < 2* target and (new_p, new_s) not in visited:
                    visited.add((new_p, new_s))
                    q.append((new_p, new_s))
            level += 1

class Solution:
    def racecar(self, target: int) -> int:
        dp = [0, 1, 4] + [float('inf')] * target
        for t in range(3, target + 1):
            k = t.bit_length()
            if t == 2**k - 1:
                dp[t] = k
                continue
            for j in range(k - 1):
                dp[t] = min(dp[t], dp[t - 2**(k - 1) + 2**j] + k - 1 + j + 2)
            if 2**k - 1 - t < t:
                dp[t] = min(dp[t], dp[2**k - 1 - t] + k + 1)
        return dp[target]
    
#         f = [None] * (target + 1)
        
#         f[0] = 0
        
#         for i in range(1, target + 1):
#             f[i] = float('inf')
            
#             n = len(bin(i)[2:])
            
#             if 2**n - 1 == i:
#                 f[i] = n
#                 continue
                
#             # overspeed
#             f[i] = f[2**n - 1 - i] + n + 1 # reverse once
            
#             # underspeed
#             for j in range(0, n):
#                 gap = 1 << j - 1
#                 f[i] = min(f[i], f[i - 2**(n - 1) + gap] + n + j + 1) # reverse twice
#         return f[target]
            
        
        
#         int[] f = new int[target + 1];
#         for (int i = 1; i <= target; i++){
#             int bound = (Integer.highestOneBit(i) << 1) - 1;
#             int n = Integer.bitCount(bound);
#             if (i == bound){
#                 f[i] = n;
#                 continue;
#             }
#             // overspeed
#             f[i] = f[bound - i] + n + 1; // Reverse once
#             // underspeed
#             bound >>= 1;
#             for (int j = 0; j < n; j++){
#                 int gap = (1 << j) - 1;
#                 f[i] = Math.min(f[i], f[i - bound + gap] + n + j + 1); // Reverse twice
#             }
#         }
#         return f[target];
#     }
# }


class Solution:
    def racecar(self, target: int) -> int:
        q = deque([(0, 1)])
        visited = set([(0, 1)])
        upper = target * 2
        
        step = 0
        while q:
            l = len(q)
            step += 1
            for _ in range(l):
                pos, speed = q.popleft()
                if pos == target:
                    return step - 1
                new_pos, new_speed = pos + speed, speed * 2
                if (new_pos, new_speed) not in visited and 0 < new_pos <= upper:
                    q.append((new_pos, new_speed))
                    visited.add((new_pos, new_speed))
                
                new_pos, new_speed = pos, -1 if speed > 0 else 1
                if (new_pos, new_speed) not in visited and 0 < new_pos <= upper:
                    q.append((new_pos, new_speed))
                    visited.add((new_pos, new_speed))
        return -1

class Solution:
    def racecar(self, target: int) -> int:
        queue = collections.deque([(1, 0)])
        visited = set(queue)
        count = 0
        while queue:
            for _ in range(len(queue)):
                speed, pos = queue.popleft()
                if pos < 0:
                    continue
                if pos > 2*target:
                    continue
                
                if target == pos:
                    return count
                
                if (speed*2, pos+speed) not in visited:
                    visited.add((speed*2, pos+speed))
                    queue.append((speed*2, pos+speed))
                
                if speed > 0:
                    if (-1, pos) not in visited:
                        visited.add((-1, pos))
                        queue.append((-1, pos))
                else:
                    if (1, pos) not in visited:
                        visited.add((1, pos))
                        queue.append((1, pos))
            count += 1
        return -1

class Solution:
    def racecar(self, target: int) -> int:
        queue = collections.deque()
        visited = set()
        queue.append((0, 1, 0))
        visited.add((0, 1))
        
        while queue:
            pos, speed, steps = queue.popleft()
            if pos == target:
                return steps
            
            next_pos = pos + speed
            next_speed = speed * 2
            if (next_pos, next_speed) not in visited and next_pos < 2 * target and next_pos > 0:
                queue.append((next_pos, next_speed, steps + 1))
                visited.add((next_pos, next_speed))
            
            next_pos = pos
            next_speed = -1 if speed > 0 else 1
            if (next_pos, next_speed) not in visited and next_pos < 2 * target and next_pos > 0:
                queue.append((next_pos, next_speed, steps + 1))
                visited.add((next_pos, next_speed))
        
        return -1


from collections import *

class Solution:
    def racecar(self, t: int) -> int:
        q, s, lvl = deque([(0, 1)]), set([(0, 1)]), 0
        
        while q:
            for _ in range(len(q)):
                pu, su = q.popleft()
                
                if pu == t:
                    return lvl
            
                a, r = (pu + su, su * 2), (pu, -1 if su > 0 else 1)
                for e in (a, r):
                    
                    if e in s or  e[0] < 0 or e[0] >= t * 2:
                        continue
                    q.append(e)
                    s.add(e)
            lvl += 1
            
        return 0


class Solution:
    def racecar(self, target: int) -> int:
        # 0 -> 1 -> 3 -> 7 - > 15
        # 1 -> 2 -> 4 -> 8 -> 16
        # 从 0 出发，每次可以 R 或 A两个方向，选择。
        # 可以记录每次到达的状态，
        # BFS
        
        d = deque([(0, 0, 1)])
        visited = collections.defaultdict(set)
        visited[0].add(1)
        ans = float('inf')
        flag = 0
        while d:
            flag += 1
            # print(\"flag=\", flag,\", d=\", d)
            l = len(d)
            while l:
                l -= 1
                cur = d.popleft()
                # print(\"cur=\", cur)
                pos, cost, speed = cur
                if pos == target:
                    ans = min(ans, cost)
                    # continue
                    return cost
                # use R
                cost += 1
                if 1:
                    newspeed = -1 if speed > 0 else 1
                    if not ((pos in visited and newspeed in visited[pos]) or (pos <= 0)):
                        # print(\"past=\", cur,\", add=\", (pos, cost, -1))
                        d.append(((pos, cost, newspeed)))
                        visited[pos].add(newspeed)
                        # 这里 if 里 break 不要瞎用，会跳出 while l 这个循环的。
                # use A
                if 1:
                    if not (( speed in visited and (cost, speed * 2) in visited[pos]) or (pos + speed > target * 2) or (pos + speed <= 0)):
                        
                        # print(\"past=\", cur,\", add=\", (pos + speed, cost, speed * 2))
                        d.append((pos + speed, cost, speed * 2))
                        visited[pos].add(speed * 2)
        return
                
  # BFS 搞了半天，终于结束了。注意要剪枝。
# 1. 首先 visited 加入的是 pos 和 speed。
# 2. 第二是 位置不能超过 target * 2
# 3. 速度不能超过 2*target。  （可以不要）
# 4. 不要 pos <0 的位置。
        # pos    0 1 3 2 3
        # speed  1 2 -1 1


from collections import deque
class Solution:
    def racecar(self, target: int) -> int:
        visited = set()
        
        q = deque([(0,1,0)])
        while q:
            pos, sp, d = q.popleft()
            #print(pos, q)
            if pos==target:
                return d

            if pos<-1 or pos>1.5*target or sp>1.5*target or (pos, sp) in visited:
                continue
            visited.add((pos, sp))

            q.append((pos+sp, sp*2, d+1))
            q.append((pos, -1*(sp//abs(sp)), d+1))


from collections import deque
class Solution:
    def racecar(self, target: int) -> int:
        queue = deque([(0, 1)])
        visited = set([(0, 1)])
        step = 0
        while queue:
            level_size = len(queue)
            # print(queue)
            for _ in range(level_size):
                posi, spd = queue.popleft()
                if posi == target:
                    return step 
                if ((posi+spd, 2*spd) not in visited) and posi+spd>0 and posi+spd < target<<1:
                    queue.append((posi+spd, 2*spd))
                    visited.add((posi+spd, 2*spd))
                sign = 1 if spd > 0 else -1 
                if ((posi, -sign) not in visited) and posi >0 and posi < target<<1:
                    queue.append((posi, -sign))
                    visited.add((posi, -sign))
            step += 1 
        return -1 

from collections import deque
class Solution:
    def racecar(self, target: int) -> int:
        visited = set()
        
        q = deque([(0,1,0)])
        while q:
            pos, sp, d = q.popleft()
            #print(pos, q)
            if pos==target:
                return d

            if (pos, sp) in visited:
                continue
            visited.add((pos, sp))
            
            if abs(sp)>target or pos<0:
                # in these cases, must turn.
                q.append((pos, -1*(sp//abs(sp)), d+1))
            else:
                # can keep goint or turn.
                q.append((pos+sp, sp*2, d+1))
                q.append((pos, -1*(sp//abs(sp)), d+1))


class Solution:
    def racecar(self, target: int) -> int:
        # 0 -> 1 -> 3 -> 7 - > 15
        # 1 -> 2 -> 4 -> 8 -> 16
        # 从 0 出发，每次可以 R 或 A两个方向，选择。
        # 可以记录每次到达的状态，
        # BFS
        
        d = deque([(0, 0, 1)])
        visited = collections.defaultdict(set)
        visited[0].add(1)
        ans = float('inf')
        flag = 0
        while d:
            flag += 1
            # print(\"flag=\", flag,\", d=\", d)
            l = len(d)
            while l:
                l -= 1
                cur = d.popleft()
                # print(\"cur=\", cur)
                pos, cost, speed = cur
                if pos == target:
                    ans = min(ans, cost)
                    # continue
                    return cost
                # use R
                cost += 1
                if 1:
                    newspeed = -1 if speed > 0 else 1
                    if not ((pos in visited and newspeed in visited[pos]) or (pos <= 0)):
                        # print(\"past=\", cur,\", add=\", (pos, cost, -1))
                        d.append(((pos, cost, newspeed)))
                        visited[pos].add(newspeed)
                        # 这里 if 里 break 不要瞎用，会跳出 while l 这个循环的。
                # use A
                if 1:
                    if not (( speed in visited and (cost, speed * 2) in visited[pos]) or (pos + speed > target * 2) or (pos + speed <= 0) or (speed > 2*target)):
                        
                        # print(\"past=\", cur,\", add=\", (pos + speed, cost, speed * 2))
                        d.append((pos + speed, cost, speed * 2))
                        visited[pos].add(speed * 2)
        return
                
        
        # pos    0 1 3 2 3
        # speed  1 2 -1 1


class Solution:
    def racecar(self, target: int) -> int:
        # 0 -> 1 -> 3 -> 7 - > 15
        # 1 -> 2 -> 4 -> 8 -> 16
        # 从 0 出发，每次可以 R 或 A两个方向，选择。
        # 可以记录每次到达的状态，
        # BFS
        
        d = deque([(0, 0, 1)])
        visited = collections.defaultdict(set)
        visited[0].add(1)
        ans = float('inf')
        flag = 0
        while d:
            flag += 1
            # print(\"flag=\", flag,\", d=\", d)
            l = len(d)
            while l:
                l -= 1
                cur = d.popleft()
                # print(\"cur=\", cur)
                pos, cost, speed = cur
                if pos == target:
                    ans = min(ans, cost)
                    # continue
                    return cost
                # use R
                cost += 1
                if 1:
                    newspeed = -1 if speed > 0 else 1
                    if not ((pos in visited and newspeed in visited[pos]) or (pos <= 0)):
                        # print(\"past=\", cur,\", add=\", (pos, cost, -1))
                        d.append(((pos, cost, newspeed)))
                        visited[pos].add(newspeed)
                        # 这里 if 里 break 不要瞎用，会跳出 while l 这个循环的。
                # use A
                if 1:
                    if not (( speed in visited and (cost, speed * 2) in visited[pos]) or (pos + speed > target * 2) or (pos + speed <= 0)):
                        
                        # print(\"past=\", cur,\", add=\", (pos + speed, cost, speed * 2))
                        d.append((pos + speed, cost, speed * 2))
                        visited[pos].add(speed * 2)
        return
                
  # BFS 搞了半天，终于结束了。注意要剪枝。
# 1. 首先 visited 加入的是 pos 和 speed。
# 2. 第二是 位置不能超过 target * 2
# 3. 速度不能超过 2*target。 
# 4. 不要 pos <0 的位置。
        # pos    0 1 3 2 3
        # speed  1 2 -1 1


class Solution:
    def racecar(self, target: int) -> int:
        dq = collections.deque([(0, 1)])
        seen = set([(0,1)])
        depth = 0
        
        while True:
            k = len(dq)
            while k:
                (pos, velo) = dq.popleft()
                if pos == target:
                    return depth
                
                cand = [(pos, -1 if velo>0 else 1)]
                if abs(target- (pos+velo)) < target:
                    cand.append((pos+velo, velo*2))
                
                for (p, v) in cand:
                    if (p, v) not in seen:
                        seen.add((p,v))
                        dq.append((p,v))    
                k-=1
                
            depth+=1 
            
        
                


class Solution:
    def racecar(self, target: int) -> int:
        queue = deque([(0,1)])
        visited=set()
        visited.add((0,1))
        step = 0
        while queue:
            for _ in range(len(queue)):
                pos, speed = queue.popleft()
                if pos+speed==target:
                    return step+1
                if abs(speed*2)<2*target and abs(pos+speed)<2*target:
                    queue.append((pos+speed,speed*2))
                if speed>0:
                    speed2=-1
                else:
                    speed2=1
                if (pos,speed2) not in visited:
                    queue.append((pos,speed2))
                    visited.add((pos,speed2))
            step+=1
        return -1


from collections import deque
class Solution:
    def racecar(self, target: int) -> int:
        visited = set()
        
        q = deque([(0,1,0)])
        while q:
            pos, sp, d = q.popleft()
            #print(pos, q)
            if pos==target:
                return d

            if pos<-1 or pos>2*target or sp>2*target or (pos, sp) in visited:
                continue
            visited.add((pos, sp))

            q.append((pos+sp, sp*2, d+1))
            q.append((pos, -1*(sp//abs(sp)), d+1))


class Solution:
    def racecar(self, target: int) -> int:
        queue = deque([(0,1)])
        visited=set()
        visited.add((0,1))
        step = 0
        while queue:
            for _ in range(len(queue)):
                pos, speed = queue.popleft()
                if pos+speed==target:
                    return step+1
                if abs(speed*2)-1<2*target and abs(pos+speed)-2<2*target:
                    queue.append((pos+speed,speed*2))
                if speed>0:
                    speed2=-1
                else:
                    speed2=1
                if (pos,speed2) not in visited:
                    queue.append((pos,speed2))
                    visited.add((pos,speed2))
            step+=1
        return -1


class Solution:
    def racecar(self, target: int) -> int:
        q = collections.deque([(0, 1, 0)])
        visited = set()
        visited.add((0,1))

        while q:
            size = len(q)
            for _ in range(size):
                pos, speed, steps = q.popleft()
                if pos == target:
                    return steps

                cand = []
                if abs(target - (pos + speed)) < target:
                    cand.append((pos + speed, 2 * speed))
                cand.append([pos, 1 if speed < 0 else -1])
                for pos, speed in cand:
                    if (pos, speed) not in visited:
                        q.append((pos, speed, steps + 1))
                        visited.add((pos, speed))
        return -1

class Solution:
    def racecar(self, target: int) -> int:
        
        def dfs(t):
            if t in dp:
                return dp[t]
            n = t.bit_length()
            if 2**n - 1 == t:
                dp[t] = n
            else:
                dp[t] = dfs(2**n - 1 - t) + n + 1
                for m in range(n - 1):
                    dp[t] = min(dp[t], dfs(t - 2**(n - 1) + 2**m) + n + m + 1)
            return dp[t]
        
        dp = {0:0}
        return dfs(target)

from collections import deque
class Solution:
    def racecar(self, target: int) -> int:
        visited = set()
        
        q = deque([(0,1,0)])
        while q:
            pos, sp, d = q.popleft()
            #print(pos, q)
            if pos==target:
                return d

            if (pos, sp) in visited:
                continue
            visited.add((pos, sp))
            
            if abs(sp)>target or pos<-1:
                # in these cases, must turn.
                q.append((pos, -1*(sp//abs(sp)), d+1))
            else:
                # can keep goint or turn.
                q.append((pos+sp, sp*2, d+1))
                q.append((pos, -1*(sp//abs(sp)), d+1))


class Solution:
    def racecar(self, target: int) -> int:
        states = set([(0, 1)])
        que = collections.deque([[0, 1]])
        cost = 0
        while que:
            for _ in range(len(que)):
                pos, speed = que.popleft()
                if pos == target:
                    return cost
                #if abs(pos) >= 2 * target:
                #    continue
                if pos < 0 or pos >= 2 * target:
                    continue
                for npos, nspeed in [[pos, 1 if speed < 0 else -1], [pos + speed, speed * 2]]:
                    if (npos, nspeed) not in states:
                        states.add((npos, nspeed))
                        que.append([npos, nspeed])
            cost += 1
        return -1

    dp = {0: 0}
    def racecar_DP(self, t):
        if t in self.dp:
            return self.dp[t]
        n = t.bit_length()
        if (1 << n) - 1 == t:
            self.dp[t] = n
        else:
            self.dp[t] = self.racecar(2**n - 1 - t) + n + 1
            for m in range(n - 1):
                self.dp[t] = min(self.dp[t], self.racecar(t - 2**(n - 1) + 2**m) + n + m + 1)
        return self.dp[t]

class Solution:
    def racecar(self, target: int) -> int:
        
        targetLen = len(bin(target)) - 2
        barrier = (1 << targetLen)
        # print(tar6021getLen, barrier)
        stack = [(0, target)]
        dp = {target:0}
        
        while stack:
            # print(stack)
            step0, dist = heapq.heappop(stack)
            
            for i in range(targetLen+1):
                move = (1<<i)-1
                step1 = step0 + i
                if move != dist:
                    step1 += 1
                newDist = -(dist - move)
                if abs(newDist) <= barrier and (newDist not in dp or dp[newDist] > step1):
                    heapq.heappush(stack, (step1, newDist))
                    dp[newDist] = step1
                    
        return dp[0]
                
                
        
        
#         stack = [(0, 0, 1)]
#         visited = {(0,1):0}
        
#         while stack:
#             stepNow, loc, speed = heapq.heappop(stack)
#             if visited[(loc, speed)] < stepNow:
#                 continue
            
#             loc1 = loc+speed
#             speed1 = speed*2
#             if loc1 == target:
#                 return stepNow + 1
#             if (loc1, speed1) not in visited or visited[(loc1, speed1)] > stepNow+1:
#                 visited[(loc1, speed1)] = stepNow + 1
#                 heapq.heappush(stack, (stepNow +1, loc1, speed1))
            
            
#             loc1 = loc
#             speed1 = -1 if speed > 0 else 1
#             if (loc1, speed1) not in visited or visited[(loc1, speed1)] > stepNow+1:
#                 visited[(loc1, speed1)] = stepNow + 1
#                 heapq.heappush(stack, (stepNow +1, loc1, speed1))


class Solution:
    def racecar(self, target: int) -> int:
        dp = [0] * (target+1)
        for i in range(1, target+1):
            dp[i] = float('inf')           
            j = 1
            m = 1
            while j < i:
                p = 0
                q = 0
                while q < j:
                    dp[i] = min(dp[i], dp[i-(j-q)] + m + 1 + p + 1)
                    p += 1
                    q = (1<<p) - 1
                m += 1
                j = (1<<m) - 1
            dp[i] = min(dp[i], m if j == i else m + 1 + dp[j-i])
        return dp[target]


class Solution:
    def racecar(self, target: int) -> int:
        dp = [0] * (target+1)
        for i in range(1, target+1):
            dp[i] = float('inf')           
            j = 1
            m = 1
            while j < i:
                p = 0
                q = 0
                while q < j:
                    dp[i] = min(dp[i], dp[i-(j-q)] + m + 1 + p + 1)
                    p += 1
                    q = (1<<p) - 1
                m += 1
                #print('j', m>>1-1, m, (m<<1) - 1)
                j = (1<<m) - 1
            #print(i, j)
            # if i == 6:
            #     print(m, dp[j-1])
            dp[i] = min(dp[i], m if j == i else m + 1 + dp[j-i])
        return dp[target]


class Solution:
    def racecar(self, tgt: int) -> int:
        
        '''
            shortest path -> bfs
        
            starting from [0, 1], how to reach tgt = 5?
            
                [0, 1] -> [1, 2], [0, -1]
                
                    [1, 2] -> [3, 4], [1, -1]
                    [0, -1] ->[-1, -2], [0, 1] ... visited
                    
                    
                        [3, 4] -> [3, -1], [7, 8]
                        [1,-1] -> [0, -2], [1, 1]
                        [-1,-2]-> [-3,-4] ... too far, [-1,1]
                        
                        
                            [3, -1] -> [2, -2], [3, 1]
                            [7,  8] ... too far
                            [0, -2] -> [-2, -4] ... too far, [0, 1] ... visited
                            [1,  1] -> [2, 2], [1, -1] ...visited
                            [-1 ,1] -> [0, 2], [-1, -1] ... too far
                            
                            
                                [2, -2] -> [0, -4], [2, 1]
                                [3,  1] -> [4,  2], [3, -1] ... visited
                                [2,  2] -> [4,  4], [2, -1]
                                [0,  2] -> [2,  4], [0, -1] ... visited
                                
                                    [0, -4] -> [-4, -8] ... too far, [0, 1] ... visited
                                    [2,  1] -> [3,   2], [2, -1]
                                    [4,  2] -> [6,   4], [4, -1]
                                    [4,  4] -> [8,   8], [4, -1] ... in queue
                                    [2, -1] -> [1,  -2], [2,  1] ... visited
                                    [2,  4] -> [6,   8], [2, -1] ... visited
                                    
                                
                                        [3, 2] -> [5 , 4]  -->> arrived
                                        
                                        -> 7 steps                                    
        '''
        
        '''
            1. try greedy -> can't pass tgt = 5
            
            2. list out all the step until reach the tgt
            
            3. speed up -> dont visit same nodes, dont go to \"too far\" nodes        
        '''    
        
        visited = dict()        
        q = collections.deque()        
        
        q.append([0, 1])        
        visited[0] = set()
        visited[0].add(1)
        
        step = 0
        while len(q) > 0:
            
            curSize = len(q)           
            
            for i in range(0, curSize):                
                
                pop = q.pop()
                pos, spd = pop[0], pop[1]
                
                if pos == tgt:
                    return step
                                                                                
                nextSteps = [ [pos + spd, spd * 2], [pos, - 1 * spd // abs(spd)] ]
                for nextStep in nextSteps:            
                    
                    nPos, nSpd = nextStep[0], nextStep[1]
                    
                    # check is too far node:
                    if abs(nPos - tgt) <= tgt:                        
                        # check visited
                        if nPos not in visited or nSpd not in visited[nPos]:
                            q.appendleft(nextStep)
                            if nPos not in visited:
                                visited[nPos] = set()
                            
                            visited[nPos].add(nSpd)
                            
            step += 1
            
            
        return -1
            
                    
                    
                    
                
            


class Solution:
    def racecar(self, target: int) -> int:
        
        def dfs(distance):
            if distance in dp:
                return dp[distance]
            position, speed, counter = 0, 1, 0
            res = float('inf')
            arr = [(0)]
            while position < distance:
                position, speed, counter = position + speed, speed*2, counter+1
                if position < distance:
                    for x in arr:
                        res = min(res, counter + 2 + dfs(distance - position + x) + dp[x])
                else:
                    res = min(res, counter + 1 + dfs(position - distance))
                arr.append(position)
            dp[distance] = res
            return res
        
        position, speed, counter = 0, 1, 0
        dp = {0:0}
        
        while position < target:
            position, speed, counter = position + speed, speed*2, counter+1
            dp[position] = counter
        return dfs(target)

class Solution:

    def racecar(self, tgt: int) -> int:
        
        '''
            shortest path -> bfs
        
            starting from [0, 1], how to reach tgt = 5?
            
                [0, 1] -> [1, 2], [0, -1]
                
                    [1, 2] -> [3, 4], [1, -1]
                    [0, -1] ->[-1, -2], [0, 1] ... visited
                    
                    
                        [3, 4] -> [3, -1], [7, 8]
                        [1,-1] -> [0, -2], [1, 1]
                        [-1,-2]-> [-3,-4] ... too far, [-1,1]
                        
                        
                            [3, -1] -> [2, -2], [3, 1]
                            [7,  8] ... too far
                            [0, -2] -> [-2, -4] ... too far, [0, 1] ... visited
                            [1,  1] -> [2, 2], [1, -1] ...visited
                            [-1 ,1] -> [0, 2], [-1, -1] ... too far
                            
                            
                                [2, -2] -> [0, -4], [2, 1]
                                [3,  1] -> [4,  2], [3, -1] ... visited
                                [2,  2] -> [4,  4], [2, -1]
                                [0,  2] -> [2,  4], [0, -1] ... visited
                                
                                    [0, -4] -> [-4, -8] ... too far, [0, 1] ... visited
                                    [2,  1] -> [3,   2], [2, -1]
                                    [4,  2] -> [6,   4], [4, -1]
                                    [4,  4] -> [8,   8], [4, -1] ... in queue
                                    [2, -1] -> [1,  -2], [2,  1] ... visited
                                    [2,  4] -> [6,   8], [2, -1] ... visited
                                    
                                
                                        [3, 2] -> [5 , 4]  -->> arrived
                                        
                                        -> 7 steps                                    
        '''
        
        '''
            1. try greedy -> can't pass tgt = 5
            
            2. list out all the step until reach the tgt -> time: O(2 ^ (num of operations) )
            
            3. speed up -> dont visit same nodes, dont go to \"too far\" nodes    
                        
            4. time complexity: 
                pos range: -tgt ~ tgt, spd range: 1 ~ log(tgt) -> graph node number will be 2 * tgt * log(tgt) -> O(tgt * log(tgt) )
                                                
        '''    
        
        visited = dict()        
        q = collections.deque()        
        
        q.append([0, 1])        
        visited[0] = set()
        visited[0].add(1)
        
        step = 0
        while len(q) > 0:
            
            curSize = len(q)           
            
            for i in range(0, curSize):                
                
                pop = q.pop()
                pos, spd = pop[0], pop[1]
                
                if pos == tgt:
                    return step
                                                                                
                nextSteps = [ [pos + spd, spd * 2], [pos, - 1 * spd // abs(spd)] ]
                for nextStep in nextSteps:            
                    
                    nPos, nSpd = nextStep[0], nextStep[1]
                    
                    # check is too far node:
                    if abs(nPos - tgt) <= tgt:                        
                        # check visited
                        if nPos not in visited or nSpd not in visited[nPos]:
                            q.appendleft(nextStep)
                            if nPos not in visited:
                                visited[nPos] = set()
                            
                            visited[nPos].add(nSpd)
                            
            step += 1
            
            
        return -1
            
                    
                    
                    
                
            


class Solution:
    def racecar(self, target: int) -> int:
        
        # position speed
        queue = [(0,1)]
        visited = set((0,1))
        step = 0
        q = 0
        
        while len(queue) >q:
            step+=1
            size = len(queue)-q
            for _ in range(size):
                x,v = queue[q]
                q+=1
                
                
                ### keep on
                x_ = x+v
                v_ = v*2
                if (x_, v_) not in visited and abs(x_)<2*target :
                    queue.append((x_,v_))
                    visited.add((x_,v_))
                    
                    if x_ == target:
                        return step
                

                #### turn
                x_  = x
                if v>0:
                    v_ = -1
                else:
                    v_ = 1
                if (x_, v_) not in visited and abs(x_)<2*target :
                    queue.append((x_,v_))
                    visited.add((x_,v_))
                    
                    if x_ == target:
                        return step
        
        


class Solution:
    def racecar(self, target: int) -> int:
        
        # position speed
        queue = [(0,1)]
        visited = set((0,1))
        step = 0
        q = 0
        
        while len(queue) >q:
            step+=1
            size = len(queue)-q
            for _ in range(size):
                x,v = queue[q]
                q+=1
                
                ### keep on
                x_ = x+v
                v_ = v*2
                # abs(x_)<2*target只是加速，不影响结果
                if (x_, v_) not in visited and abs(x_)<2*target :
                    queue.append((x_,v_))
                    visited.add((x_,v_))
                    
                    if x_ == target:
                        return step
                

                #### turn
                x_  = x
                if v>0:
                    v_ = -1
                else:
                    v_ = 1
                # abs(x_)<2*target只是加速，不影响结果
                if (x_, v_) not in visited and abs(x_)<2*target :
                    queue.append((x_,v_))
                    visited.add((x_,v_))
                    
                    if x_ == target:
                        return step
        
        


class Solution:

    def racecar(self, tgt: int) -> int:
        
        '''
            shortest path -> bfs
        
            starting from [0, 1], how to reach tgt = 5?
            
                [0, 1] -> [1, 2], [0, -1]
                
                    [1, 2] -> [3, 4], [1, -1]
                    [0, -1] ->[-1, -2], [0, 1] ... visited
                    
                    
                        [3, 4] -> [3, -1], [7, 8]
                        [1,-1] -> [0, -2], [1, 1]
                        [-1,-2]-> [-3,-4] ... too far, [-1,1]
                        
                        
                            [3, -1] -> [2, -2], [3, 1]
                            [7,  8] ... too far
                            [0, -2] -> [-2, -4] ... too far, [0, 1] ... visited
                            [1,  1] -> [2, 2], [1, -1] ...visited
                            [-1 ,1] -> [0, 2], [-1, -1] ... too far
                            
                            
                                [2, -2] -> [0, -4], [2, 1]
                                [3,  1] -> [4,  2], [3, -1] ... visited
                                [2,  2] -> [4,  4], [2, -1]
                                [0,  2] -> [2,  4], [0, -1] ... visited
                                
                                    [0, -4] -> [-4, -8] ... too far, [0, 1] ... visited
                                    [2,  1] -> [3,   2], [2, -1]
                                    [4,  2] -> [6,   4], [4, -1]
                                    [4,  4] -> [8,   8], [4, -1] ... in queue
                                    [2, -1] -> [1,  -2], [2,  1] ... visited
                                    [2,  4] -> [6,   8], [2, -1] ... visited
                                    
                                
                                        [3, 2] -> [5 , 4]  -->> arrived
                                        
                                        -> 7 steps                                    
        '''
        
        '''
            1. try greedy -> can't pass tgt = 5
            
            2. list out all the step until reach the tgt -> time: O(2 ^ (num of operations) )
            
            3. speed up -> dont visit same nodes, dont go to \"too far\" nodes                        
        '''    
        
        visited = dict()        
        q = collections.deque()        
        
        q.append([0, 1])        
        visited[0] = set()
        visited[0].add(1)
        
        step = 0
        while len(q) > 0:
            
            curSize = len(q)           
            
            for i in range(0, curSize):                
                
                pop = q.pop()
                pos, spd = pop[0], pop[1]
                
                if pos == tgt:
                    return step
                                                                                
                nextSteps = [ [pos + spd, spd * 2], [pos, - 1 * spd // abs(spd)] ]
                for nextStep in nextSteps:            
                    
                    nPos, nSpd = nextStep[0], nextStep[1]
                    
                    # check is too far node:
                    if abs(nPos - tgt) <= tgt:                        
                        # check visited
                        if nPos not in visited or nSpd not in visited[nPos]:
                            q.appendleft(nextStep)
                            if nPos not in visited:
                                visited[nPos] = set()
                            
                            visited[nPos].add(nSpd)
                            
            step += 1
            
            
        return -1
            
                    
                    
                    
                
            


from collections import deque
class Solution:
    def racecar(self, target: int) -> int:
        
        steps = 0
        queue = deque([(0, 1)])
        cache = {(0,1)}
        while queue:
            for _ in range(len(queue)):
                p, s = queue.popleft()
                if p == target:
                    return steps
                p1,s1 = p+s, s*2
                p2 = p
                s2 = -1 if s > 0 else 1
                
                if -10000 <= p1 <= 10000 and (p1,s1) not in cache:
                    cache.add((p1,s1))
                    queue.append((p1,s1))
                if -10000 <= p2 <= 10000 and  (p2,s2) not in cache:
                    cache.add((p2,s2))
                    queue.append((p2,s2))
            steps += 1

                
            
            


from collections import deque
class Solution:
    # def racecar(self, target: int) -> int:
    #     # position, speed
    #     queue = deque([(0,1)])
    #     nsteps = -1
    #     while queue:
    #         levelSize = len(queue)
    #         nsteps += 1
    #         for _ in range(levelSize):
    #             pos, speed = queue.popleft()
    #             if pos == target:
    #                 return nsteps
    #             # Always consider moving the car in the direction it is already going
    #             queue.append( (pos+speed, speed*2) )
    #             # Only consider changing the direction of the car if one of the following conditions is true
    #             if (pos>target and speed>0) or \\
    #                (pos<target and speed<0) or \\
    #                (pos+speed>target and speed>0) or \\
    #                (pos+speed<target and speed<0):
    #                 queue.append( (pos, -1 if speed>0 else 1) )
    #     return nsteps
    def __init__(self):
        self.dp = {0: 0}
    def racecar(self, t: int) -> int:
        if t in self.dp:
            return self.dp[t]

        n = t.bit_length()
        if 2**n - 1 == t:
            self.dp[t] = n
        else:
            # go pass the target, stop and turn back
            self.dp[t] = self.racecar(2**n-1-t) + n + 1
            # Go as far as possible before pass target, stop and turn back
            for m in range(n-1):
                self.dp[t] = min(self.dp[t], self.racecar(t - 2**(n-1) + 1 + 2**m - 1) + (n - 1) + m + 2)
        return self.dp[t]


class Solution:
    def racecar(self, target: int) -> int:
        been = set()
        steps = 0
        queue = {(target, 1)}
        while queue:
            print(len(queue))
            newQueue = set()
            for pos, speed in queue:
                if pos == 0: return steps
                been.add((pos, speed))
                nextStatus = (abs(pos - speed), -speed * 2 if speed > pos else speed * 2)
                if nextStatus[0] < target * 2 and nextStatus not in been:
                    newQueue.add(nextStatus)
                nextStatus = (pos, -1 if speed > 0 else 1)
                if nextStatus[0] < target * 2 and nextStatus not in been:
                    newQueue.add(nextStatus)
            steps += 1
            queue = newQueue

class Solution:
    def racecar(self, target: int) -> int:
        K = target.bit_length()+1
        barrier = 1 << K
        pq = [(0, target)]
        dist = [float('inf')] * (2*barrier + 1)
        dist[target] = 0
        
        while pq:
            steps, targ = heapq.heappop(pq)
            if dist[targ] < steps: continue
            
            for k in range(K+1):
                walk = (1<<k)-1
                steps2, targ2 = steps+k+1, walk - targ
                if walk == targ: steps2 -= 1
                
                if abs(targ2) <= barrier and steps2 < dist[targ2]:
                    heapq.heappush(pq, (steps2, targ2))
                    dist[targ2] = steps2
        
        return dist[0]
            
        
        
        


class Solution:
    def racecar(self, target: int) -> int:
        K = target.bit_length() + 1
        barrier = 1 << K
        pq = [(0, target)]
        dist = [float('inf')] * (2 * barrier + 1)
        dist[target] = 0

        while pq:
            steps, targ = heapq.heappop(pq)
            if dist[targ] < steps: continue

            for k in range(K+1):
                walk = (1 << k) - 1
                steps2, targ2 = steps + k + 1, walk - targ
                if walk == targ: steps2 -= 1 #No \"R\" command if already exact

                if abs(targ2) <= barrier and steps2 < dist[targ2]:
                    heapq.heappush(pq, (steps2, targ2))
                    dist[targ2] = steps2

        return dist[0]
            
        
        
        


class Solution:
    def racecar(self, t: int) -> int:
        q=[(0,1,0)]
        seen={}
        while q:
            c,s,step=q.pop(0)
            if (c,s) in seen: continue
            else: seen[(c,s)]=step

            if c==t: return step
            step+=1
            
            # A
            c1=c+s
            s1=s*2
            if abs(c+s-t) < t and (c1,s1) not in seen:
                q.append((c1,s1,step))
            # R
            s2=-1 if s>0 else 1
            if abs(c-t) < t and (c,s2) not in seen:
                q.append((c,s2,step))
        return -1


class Solution:
    def racecar(self, target: int) -> int:
        import heapq
        K = target.bit_length() + 1
        barrier = 1 << K
        pq = [(0, target)]
        dist = [float('inf')] * (2 * barrier + 1)
        dist[target] = 0

        while pq:
            steps, targ = heapq.heappop(pq)
            if dist[targ] > steps:
                continue

            for k in range(K+1):
                walk = (1 << k) - 1
                steps2, targ2 = steps + k + 1, walk - targ
                if walk == targ:
                    steps2 -= 1 #No \"R\" command if already exact

                if abs(targ2) <= barrier and steps2 < dist[targ2]:
                    heapq.heappush(pq, (steps2, targ2))
                    dist[targ2] = steps2

        return dist[0]

class Solution:
    def racecar(self, target: int) -> int:
        K = target.bit_length() + 1
        barrier = 1 << K
        pq = [(0, target)]
        dist = [float('inf')] * (2 * barrier + 1)
        dist[target] = 0

        while pq:
            steps, targ = heapq.heappop(pq)
            if dist[targ] > steps: continue

            for k in range(K+1):
                walk = (1 << k) - 1
                steps2, targ2 = steps + k + 1, walk - targ
                if walk == targ: steps2 -= 1 #No \"R\" command if already exact

                if abs(targ2) <= barrier and steps2 < dist[targ2]:
                    heapq.heappush(pq, (steps2, targ2))
                    dist[targ2] = steps2

        return dist[0]
            
        
        
        


class Solution:
    def racecar(self, target: int) -> int:
        st = [(0, 1, '')]
        visited = set()

        while st:
            a = st.pop(0)
            if a[0] == target:
                return len(a[2])
            # put a 'A'
            if 0 <= a[0] + a[1] < 2 * target and (a[0] + a[1], a[1] * 2) not in visited:
                st.append((a[0] + a[1], a[1] * 2, a[2] + 'A'))
                visited.add((a[0] + a[1], a[1] * 2))

            # put a 'R'
            if a[0] >= 0 and (a[0], -1 if a[1] > 0 else 1) not in visited:
                st.append((a[0], -1 if a[1] > 0 else 1, a[2] + 'R'))
                visited.add((a[0], -1 if a[1] > 0 else 1))

        return -1

class Solution:
    def racecar(self, target: int) -> int:
        K = target.bit_length() + 1
        barrier = 1 << K
        pq = [(0, target)]
        dist = [float('inf')] * (2 * barrier + 1)
        dist[target] = 0

        while pq:
            steps, targ = heapq.heappop(pq)
            if dist[targ] > steps: continue

            for k in range(K+1):
                walk = (1 << k) - 1
                steps2, targ2 = steps + k + 1, walk - targ
                if walk == targ: steps2 -= 1 #No \"R\" command if already exact

                if abs(targ2) <= barrier and steps2 < dist[targ2]:
                    heapq.heappush(pq, (steps2, targ2))
                    dist[targ2] = steps2

        return dist[0]

class Solution:
    def racecar(self, target: int) -> int:
        K = target.bit_length() + 1
        barrier = 1 << K
        pq = [(0, target)]
        dist = [float('inf')] * (2 * barrier + 1)
        dist[target] = 0

        while pq:
            steps, targ = heapq.heappop(pq)
            #if dist[targ] < steps: continue

            for k in range(K+1):
                walk = (1 << k) - 1
                steps2, targ2 = steps + k + 1, walk - targ
                if walk == targ: steps2 -= 1 #No \"R\" command if already exact

                if abs(targ2) <= barrier and steps2 < dist[targ2]:
                    heapq.heappush(pq, (steps2, targ2))
                    dist[targ2] = steps2

        return dist[0]
            
        
        
        


class Solution(object):
    def racecar(self, target):
        K = target.bit_length() + 1
        barrier = 1 << K
        pq = [(0, target)]
        dist = [float('inf')] * (2 * barrier + 1)
        dist[target] = 0

        while pq:
            steps, targ = heapq.heappop(pq)
            if dist[targ] > steps: continue

            for k in range(K+1):
                walk = (1 << k) - 1
                steps2, targ2 = steps + k + 1, walk - targ
                if walk == targ: steps2 -= 1 #No \"R\" command if already exact

                if abs(targ2) <= barrier and steps2 < dist[targ2]:
                    heapq.heappush(pq, (steps2, targ2))
                    dist[targ2] = steps2

        return dist[0]

class Solution:
    def racecar(self, target):
        K = target.bit_length() + 1
        barrier = 2**K
        pq = [(0, target)]
        dist = [float('inf')] * (2 * barrier + 1)
        dist[target] = 0

        while pq:
            steps, targ = heapq.heappop(pq)
            if dist[targ] > steps: continue

            for k in range(K+1):
                walk = (1 << k) - 1
                steps2, targ2 = steps + k + 1, walk - targ
                if walk == targ: steps2 -= 1 #No \"R\" command if already exact

                if abs(targ2) <= barrier and steps2 < dist[targ2]:
                    heapq.heappush(pq, (steps2, targ2))
                    dist[targ2] = steps2

        return dist[0]

class Solution:
    def racecar(self, target: int) -> int:
        K = target.bit_length() + 1
        barrier = 1 << K
        pq = [(0, target)]
        dist = [float('inf')] * (2 * barrier + 1)
        dist[target] = 0

        while pq:
            steps, targ = heapq.heappop(pq)
            if dist[targ] > steps: continue

            for k in range(K+1):
                walk = (1 << k) - 1
                steps2, targ2 = steps + k + 1, walk - targ
                if walk == targ: steps2 -= 1 #No \"R\" command if already exact

                if abs(targ2) <= barrier and steps2 < dist[targ2]:
                    heapq.heappush(pq, (steps2, targ2))
                    dist[targ2] = steps2

        return dist[0]
            
                    
                    
                
                
                
            


class Solution:
    def racecar(self, target):
        K = target.bit_length() + 1
        barrier = 1 << K
        pq = [(0, target)]
        dist = [float('inf')] * (2 * barrier + 1)
        dist[target] = 0

        while pq:
            steps, targ = heapq.heappop(pq)
            if dist[targ] > steps: continue

            for k in range(K+1):
                walk = (1 << k) - 1
                steps2, targ2 = steps + k + 1, walk - targ
                if walk == targ: steps2 -= 1 #No \"R\" command if already exact

                if abs(targ2) <= barrier and steps2 < dist[targ2]:
                    heapq.heappush(pq, (steps2, targ2))
                    dist[targ2] = steps2

        return dist[0]

class Solution:
    def racecar(self, target: int) -> int:
        boundary = 2*target+1
        forw_stat = [target*3] * boundary
        back_stat = [target*3] * boundary
        actions = []
        _s = 1
        queue = []
        while True:
            _jump  = 2**_s - 1
            if _jump >= boundary: break
            actions.append((_jump, _s))  # jump, step
            actions.append((-_jump, _s)) 
            queue.append((_s, _jump, 1))
            forw_stat[_jump] = _s
            _s += 1
        # print(actions)
        # --
        import heapq
        heapq.heapify(queue)
        while len(queue)>0:
            step, posi, is_forw = heapq.heappop(queue)
            # --
            for _jump, _step in actions:
                if _jump * is_forw > 0:
                    next_step, next_posi, next_is_forw = (step+_step+2, posi+_jump, is_forw)
                else:
                    next_step, next_posi, next_is_forw = (step+_step+1, posi+_jump, -is_forw)
                # --
                if next_posi<0 or next_posi>=boundary: continue
                cur_stat = forw_stat if next_is_forw==1 else back_stat
                if next_step < cur_stat[next_posi]:
                    cur_stat[next_posi] = next_step
                    heapq.heappush(queue, (next_step, next_posi, next_is_forw))
        # --
        return min(forw_stat[target], back_stat[target])


from collections import deque
class Solution:
    def racecar(self, target: int) -> int:
        visited = set()
        
        q = deque([(0,1,0)])
        while q:
            pos, sp, d = q.popleft()
            #print(pos, q)
            if pos==target:
                return d

            if (pos, sp) in visited:
                continue
            visited.add((pos, sp))
            
            if abs(sp)>target:
                # in these cases, must turn.
                q.append((pos, -1*(sp//abs(sp)), d+1))
            else:
                # can keep goint or turn.
                q.append((pos+sp, sp*2, d+1))
                q.append((pos, -1*(sp//abs(sp)), d+1))