Getting Zero (Codeforces 1661B)
Tags: Greedy, shortest paths

Suppose you have an integer $$$v$$$. In one operation, you can:   either set $$$v = (v + 1) \bmod 32768$$$  or set $$$v = (2 \cdot v) \bmod 32768$$$. You are given $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$. What is the minimum number of operations you need to make each $$$a_i$$$ equal to $$$0$$$?

Input: The first line contains the single integer $$$n$$$ ($$$1 \le n \le 32768$$$) — the number of integers.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < 32768$$$).

Output: Print $$$n$$$ integers. The $$$i$$$-th integer should be equal to the minimum number of operations required to make $$$a_i$$$ equal to $$$0$$$.

Note: Let's consider each $$$a_i$$$:   $$$a_1 = 19$$$. You can, firstly, increase it by one to get $$$20$$$ and then multiply it by two $$$13$$$ times. You'll get $$$0$$$ in $$$1 + 13 = 14$$$ steps.  $$$a_2 = 32764$$$. You can increase it by one $$$4$$$ times: $$$32764 \rightarrow 32765 \rightarrow 32766 \rightarrow 32767 \rightarrow 0$$$.  $$$a_3 = 10240$$$. You can multiply it by two $$$4$$$ times: $$$10240 \rightarrow 20480 \rightarrow 8192 \rightarrow 16384 \rightarrow 0$$$.  $$$a_4 = 49$$$. You can multiply it by two $$$15$$$ times. 

Sample Inputs:
4
19 32764 10240 49

Sample Outputs:
14 4 4 15

Solution (Python):
import sys

def solve():
    MOD = 32768
    dp = [None] * MOD
    dp[0] = 0
    q = [0]
    qi = 0
    while qi < len(q):
        x = q[qi]
        qi += 1
        tmp = [(x - 1) % MOD]
        if x % 2 == 0:
            tmp.append(x // 2)
            tmp.append(x // 2 + MOD // 2)
        for y in tmp:
            if dp[y] is None:
                dp[y] = dp[x] + 1
                q.append(y)
    inp = sys.stdin.readline
    n = int(inp())
    print(' '.join((str(dp[i]) for i in map(int, inp().split()))))

def main():
    solve()
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
flag = [0] + [-1] * 32767
q = deque([(32768, 0)])
while len(q) > 0:
    (a, b) = q.popleft()
    if a % 2 == 0 and flag[a // 2] == -1:
        flag[a // 2] = b + 1
        q.append((a // 2, b + 1))
    if a < 32768 and (a + 32768) % 2 == 0 and (flag[(a + 32768) // 2] == -1):
        flag[(a + 32768) // 2] = b + 1
        q.append(((a + 32768) // 2, b + 1))
    if a >= 1 and flag[a - 1] == -1:
        flag[a - 1] = b + 1
        q.append((a - 1, b + 1))
ans = []
int(input())
l = list(map(int, input().split()))
for x in l:
    ans.append(flag[x])
print(*ans)

Solution (Python):
n = int(input())
a = map(int, input().split())
c = 32768
arr = [[] for i in range(c)]
for i in range(c):
    arr[(i + 1) % c].append(i)
    arr[2 * i % c].append(i)
dist = [-1] * c
active = [0]
counter = 0
while len(active) != 0:
    nextactive = []
    for at in active:
        if dist[at] == -1:
            dist[at] = counter
            for e in arr[at]:
                nextactive.append(e)
    active = nextactive.copy()
    counter += 1
for j in a:
    print(dist[j], end=' ')