Problem:


Problem F: Power Calculus

Starting with x and repeatedly multiplying by x, we can compute x31 with thirty multiplications:

      x2 = x &times; x, x3 = x2 &times;  x, x4 = x3 &times; x, ... , x31 = x30 &times;  x.

The operation of squaring can appreciably shorten the sequence of multiplications. The following is a way to compute x31 with eight multiplications:

      x2 = x &times; x, x3 = x2 &times; x, x6 = x3 &times; x3, x7 = x6 &times; x, x14 = x7 &times; x7,

      x15 = x14 &times; x, x30 = x15 &times; x15, x31 = x30 &times; x.

This is not the shortest sequence of multiplications to compute x31. There are many ways with only seven multiplications. The following is one of them:

      x2 = x &times; x, x4 = x2 &times; x2, x8 = x4 &times; x4, x10 = x8 &times; x2,

      x20 = x10 &times; x10, x30 = x20 &times; x10, x31 = x30 &times; x.

There however is no way to compute x31 with fewer multiplications. Thus this is one of the
most eficient ways to compute x31 only by multiplications.

If division is also available, we can find a shorter sequence of operations. It is possible to
compute x31 with six operations (five multiplications and one division):

      x2 = x &times; x, x4 = x2 &times; x2, x8 = x4 &times; x4, x16 = x8 &times; x8, x32  = x16 &times; x16,

      x31 = x32 &divide; x.

This is one of the most eficient ways to compute x31 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 xn
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 xn 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



Sample input:
1
31
70
91
473
512
811
953
0


Sample output:
0
6
8
9
11
9
13
12

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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]