Problem:
Problem F: Power Calculus Starting with x and repeatedly multiplying by x , we can compute x 31 with thirty multiplications:   x 2 = x × x , x 3 = x 2 × x , x 4 = x 3 × x , ... , x 31 = x 30 × x .  The operation of squaring can appreciably shorten the sequence of multiplications. The following is a way to compute x 31 with eight multiplications:   x 2 = x × x , x 3 = x 2 × x , x 6 = x 3 × x 3 , x 7 = x 6 × x , x 14 = x 7 × x 7 ,  x 15 = x 14 × x , x 30 = x 15 × x 15 , x 31 = x 30 × x .  This is not the shortest sequence of multiplications to compute x 31 . There are many ways with only seven multiplications. The following is one of them:   x 2 = x × x , x 4 = x 2 × x 2 , x 8 = x 4 × x 4 , x 10 = x 8 × x 2 ,  x 20 = x 10 × x 10 , x 30 = x 20 × x 10 , x 31 = x 30 × x .  There however is no way to compute x 31 with fewer multiplications. Thus this is one of the
most eficient ways to compute x 31 only by multiplications. If division is also available, we can find a shorter sequence of operations. It is possible to
compute x 31 with six operations (five multiplications and one division):   x 2 = x × x , x 4 = x 2 × x 2 , x 8 = x 4 × x 4 , x 16 = x 8 × x 8 , x 32 = x 16 × x 16 ,  x 31 = x 32 ÷ x .  This is one of the most eficient ways to compute x 31 if a division is as fast as a multiplication. Your mission is to write a program to find the least number of operations to compute x n by multiplication and division starting with x for the given positive integer n . Products and
quotients appearing in the sequence of operations should be x to a positive integer's power. In
other words, x -3 , for example, should never appear. Input The input is a sequence of one or more lines each containing a single integer n . n is positive and
less than or equal to 1000. The end of the input is indicated by a zero. Output Your program should print the least total number of multiplications and divisions required to
compute x n starting with x for the integer n . The numbers should be written each in a separate
line without any superfluous characters such as leading or trailing spaces. Sample Input 1
31
70
91
473
512
811
953
0 Output for the Sample Input 0
6
8
9
11
9
13
12

Solution (Python):
from collections import deque

number_list = [float("inf") for i in range(1000 + 1)]
number_list[1] = 0
que = deque([[1, [1], 0]])


while len(que) > 0:
    n, array, depth = que.popleft()
    if depth > 16:
        continue
    for i in array:
        if n + i <= 1000 and number_list[n + i] >= depth + 1:
            number_list[n + i] = depth + 1
            que.append([n + i, array + [n + i], depth + 1])

        if n - i > 0 and number_list[n - i] >= depth + 1:
            number_list[n - i] = depth + 1
            que.append([n - i, array + [n - i], depth + 1])


while True:
    N = int(input())
    if N == 0:
        break
    print(number_list[N])

Solution (Python):
def motomeruyuo():
    d = deque([(0, 1, [1])])
    num_list = [float('inf') for i in range(2001)]
    num_list[1] = 0
    
    while d:
        times, now, nums = d.popleft()

        for i in nums:
            tmp = i + now
            if tmp > 2000:
                continue
            if num_list[tmp] >= times:
                num_list[tmp] = times
                d.append((times + 1, tmp, nums + [tmp]))

        for i in nums:
            tmp = max(now - i, i - now)
            if tmp <= 0:
                continue
            if num_list[tmp] >= times:
                num_list[tmp] = times
                d.append((times + 1, tmp, nums + [tmp]))
        
    return num_list

from collections import deque

ans = []

num_list = motomeruyuo()
while True:
    a = int(input())
    if not a:
        break
    
    if a == 1:
        ans.append(num_list[a])
    else:
        ans.append(num_list[a] + 1)

[print(i) for i in ans]